Merge K Sorted Linked Lists

The problem, simply

You get k linked lists. Each list is a chain of boxes sorted from small to big. Join all the boxes into one chain, still sorted, and return its head. Let N be the total number of boxes.

For lists 1 -> 4 -> 5, 1 -> 3 -> 4 and 2 -> 6, the answer is 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6.

A story to remember it

Picture it

Examples

Way 1: the simple way

Copy every value into an array, sort it, and build a brand new chain.

1. Walk every list and collect all N values.
2. Sort them.
3. Make a new node for each value and link them.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> vals = new ArrayList<>();
        for (ListNode head : lists) {
            for (ListNode cur = head; cur != null; cur = cur.next) vals.add(cur.val);
        }
        Collections.sort(vals);
        ListNode dummy = new ListNode(0), tail = dummy;
        for (int v : vals) {
            tail.next = new ListNode(v);   // brand new boxes
            tail = tail.next;
        }
        return dummy.next;
    }
}

How long it takes: sorting N values is O(N log N). Extra room: the array and the new nodes, O(N). It also throws away the fact that each list was sorted.

Way 2: the clever way

Keep the heads of all lists in a min heap ordered by value. The top is always the smallest box that is left.

1. Put every non-null head into the min heap.
2. Make a dummy box and a tail finger on it.
3. While the heap is not empty:
   • Poll the smallest box and hook it after tail. Move tail to it.
   • If that box has a next, offer next into the heap.
4. Return dummy.next.

No new boxes are made. We only change arrows.

import java.util.PriorityQueue;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
        for (ListNode head : lists) {
            if (head != null) heap.offer(head);      // only real heads
        }
        ListNode dummy = new ListNode(0), tail = dummy;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();             // smallest front box
            tail.next = node;                        // hook it on
            tail = node;
            if (node.next != null) heap.offer(node.next); // its list sends the next box
        }
        return dummy.next;
    }
}

How long it takes: every one of the N boxes goes into the heap once and out once, and the heap never holds more than k boxes, so O(N log k). Extra room: the heap, O(k). The answer reuses the old boxes.

Another way: merge in pairs

Merge list 0 with list 1, list 2 with list 3, and so on. Then merge the results in pairs again, like the rounds of a tournament, until one list is left. Each round touches all N boxes and there are log k rounds, so this is also O(N log k), with only O(log k) room for the recursion and no heap.

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        return mergeRange(lists, 0, lists.length - 1);
    }

    private ListNode mergeRange(ListNode[] lists, int lo, int hi) {
        if (lo == hi) return lists[lo];
        int mid = lo + (hi - lo) / 2;
        return mergeTwo(mergeRange(lists, lo, mid), mergeRange(lists, mid + 1, hi));
    }

    private ListNode mergeTwo(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0), tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = (a != null) ? a : b;   // hook on whatever is left
        return dummy.next;
    }
}

Watch out for

• Merging the lists one after another into a growing answer is O(N k), because the early boxes are walked again in every merge. Pair them up instead, or use the heap.
• Compare with Integer.compare(a.val, b.val). a.val - b.val overflows for values near the int limits.
• The dummy box saves you from a special case for the first box. Return dummy.next, not dummy.
• Equal values from different lists can come out in either order. If that order matters, break ties with the list number.

What interviewers ask next

• Heap or pairwise merging? Both are O(N log k). The heap handles lists that arrive over time. Pairwise merging uses O(log k) room and no heap.
• What if k is huge and lists are tiny? The log k part dominates. Pairwise merging and the heap are still the best you can do with comparisons.
• What if the lists live on different machines? Each machine sends its smallest remaining value. A coordinator runs the heap. This is how distributed sorts merge their pieces.
• Sort one linked list? Use merge sort: split with fast and slow pointers, sort each half, and merge with mergeTwo, O(n log n).
• Merge k sorted arrays? The same heap, but each entry also stores which array and which position it came from.

Remember this

Grown-up words: the trains are sorted linked lists, the tray is a min heap (priority queue) of size k, hooking a car on is relinking tail.next, the starting box is a dummy node, and the whole idea is a k-way merge.