Sort a k sorted doubly linked list

JavaView on GFG

Intuition

Sort doubly linked list where each element is at most k positions from its correct position. Min-heap of size k+1.

Algorithm

1Add first k+1 nodes to min-heap. Pop minimum to result, add next node from list. Repeat.

Common Pitfalls

•O(n log k). Same as nearly sorted array but on DLL. Maintain k+1 size heap while traversing.

Sort a k sorted doubly linked list.java

Java

// Approach: Min-heap of size k+1. Extract min, insert next element from its source into heap.
// Time: O(n log k) Space: O(k)

// User function Template for Java
class Solution {
    public DLLNode sortAKSortedDLL(DLLNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }

        PriorityQueue<DLLNode> minHeap = new PriorityQueue<>((a, b) -> a.data - b.data);
        DLLNode newHead = null, last = null;

        // Add first k+1 elements to the min heap
        for (int i = 0; i <= k && head != null; i++) {
            minHeap.add(head);
            head = head.next;
        }

        // Process the remaining elements
        while (!minHeap.isEmpty()) {
            if (newHead == null) {
                newHead = minHeap.poll();
                newHead.prev = null;
                last = newHead;
            } else {
                last.next = minHeap.poll();
                last.next.prev = last;
                last = last.next;
            }

            if (head != null) {
                minHeap.add(head);
                head = head.next;
            }
        }
        last.next = null;

        return newHead;
    }
}

Was this solution helpful?