Sort a k sorted Doubly Linked list

The problem, simply

You get a doubly linked list (each box has next and prev arrows) and a number k. The chain is almost sorted: every box is at most k places away from the spot it would have in the sorted chain.

Sort the chain from small to big, fix every next and prev arrow, and give back the new head. Use the "almost sorted" hint to be faster than a normal sort.

A story to remember it

Picture it

Examples

Way 1: the simple way

Ignore the hint. Copy all the numbers out, sort them, and write them back.

1. Walk the chain and put every number in a list.
2. Sort the list.
3. Walk the chain again and write the sorted numbers into the boxes.

import java.util.*;

class Solution {
    public Node sortKSorted(Node head, int k) {
        List<Integer> nums = new ArrayList<>();
        for (Node cur = head; cur != null; cur = cur.next) nums.add(cur.data);
        Collections.sort(nums);                       // a normal full sort
        int i = 0;
        for (Node cur = head; cur != null; cur = cur.next) cur.data = nums.get(i++);
        return head;
    }
}

How long it takes: the sort is O(n log n). Extra room: the copy of all numbers, O(n). It throws away the hint that the chain is almost sorted.

Way 2: the clever way

The smallest box of the whole chain must be among the first k + 1 boxes, because it is at most k places from the front. The same is true for every next smallest box. So keep a small pile, a min heap, that always holds the next k + 1 boxes and gives back the smallest one fast.

1. Put the first k + 1 boxes into the min heap.
2. Take the smallest box out and hook it to the end of the sorted chain, fixing both next and prev.
3. If boxes are left in the input, put the next one into the heap.
4. Repeat until the heap is empty. Set the last box's next to null.

import java.util.*;

class Solution {
    public Node sortKSorted(Node head, int k) {
        if (head == null) return null;
        PriorityQueue<Node> pile = new PriorityQueue<>((a, b) -> Integer.compare(a.data, b.data));
        Node curr = head;
        for (int i = 0; i <= k && curr != null; i++) {   // the first k + 1 boxes
            pile.offer(curr);
            curr = curr.next;
        }
        Node newHead = null, tail = null;
        while (!pile.isEmpty()) {
            Node small = pile.poll();                      // the next smallest box
            if (newHead == null) { newHead = small; small.prev = null; }
            else { tail.next = small; small.prev = tail; } // hook both arrows
            tail = small;
            if (curr != null) {                            // keep the pile full
                pile.offer(curr);
                curr = curr.next;
            }
        }
        tail.next = null;
        return newHead;
    }
}

Reading curr.next is safe even while we rewire, because we only change the arrows of boxes that already left the pile, and curr is always ahead of them. How long it takes: each of the n boxes goes into a pile of at most k + 1 boxes and comes out once, and each of those costs O(log k), so O(n log k). Extra room: the pile, O(k).

Another way: insertion sort with the back arrows

A doubly list can walk backwards, so insertion sort fits it well. Take each box and walk back with prev until you find a smaller number, then move the box there. Since every box is at most k places off, each walk back is at most k steps. This takes O(n * k) time and O(1) room, which beats the heap when k is tiny, like 1 or 2.

class Solution {
    public Node sortKSorted(Node head, int k) {
        if (head == null) return null;
        Node cur = head.next;
        while (cur != null) {
            Node next = cur.next;
            Node spot = cur.prev;
            while (spot != null && spot.data > cur.data) spot = spot.prev;   // at most k steps
            if (spot != cur.prev) {
                cur.prev.next = cur.next;                  // unhook cur
                if (cur.next != null) cur.next.prev = cur.prev;
                if (spot == null) {                        // cur becomes the new head
                    cur.prev = null; cur.next = head; head.prev = cur; head = cur;
                } else {                                   // put cur right after spot
                    cur.next = spot.next; cur.prev = spot;
                    spot.next.prev = cur; spot.next = cur;
                }
            }
            cur = next;
        }
        return head;
    }
}

Watch out for

• Fix both arrows when hooking a box: tail.next = small and small.prev = tail. The new head needs prev = null and the last box needs next = null.
• (a, b) -> a.data - b.data can overflow for very large or very negative numbers. Use Integer.compare.
• Equal numbers: the heap is not stable, so equal boxes can swap places. The insertion sort way keeps them in order.

What interviewers ask next

• Why does this work? The box that belongs at position i sits somewhere between i - k and i + k. When we fill position i, every box up to i + k has been read, so it is in the pile or already placed.
• Merge k sorted lists (LeetCode 23). Same pile, but it holds the front box of each list.
• Sort a nearly sorted array. The same pile of k + 1, writing back into the array.
• Heap or insertion sort? Heap is O(n log k), insertion sort is O(n k) with no extra room. For k of 1 or 2 insertion sort wins; for larger k the heap wins.
• What if k is unknown? You cannot use the window trick safely. Fall back to merge sort on the list, O(n log n).

Remember this

Grown-up words: the pile that always hands out the smallest is a min heap or priority queue, the boxes are nodes with prev and next pointers, "every box at most k places off" is a k-sorted list, and walking back to place each box is insertion sort.