Merge K sorted Linked list

The problem, simply

You get k linked lists. Each one is sorted from small to big. Join all their boxes into one sorted list and return its head. Reuse the boxes you were given and only rewire the arrows.

Call the total number of boxes in all lists N.

A story to remember it

Picture it

Examples

Way 1: the simple way

Merge the lists one at a time, using the merge step from merge sort.

1. Start with the answer equal to the first list.
2. Merge the answer with the second list. Then merge that with the third list, and so on.
3. Each merge walks two sorted lists with two fingers and always takes the smaller front box.

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode answer = null;
        for (ListNode list : lists) answer = mergeTwo(answer, list);   // one at a time
        return answer;
    }

    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;    // glue on whatever is left
        return dummy.next;
    }
}

How long it takes: the answer grows each round and is walked again each round. With k lists of equal size that adds up to about N * k / 2 steps, O(N k). Extra room: a few fingers, O(1).

Way 2: the clever way

Use the lunch lady's podium: a min heap, also called a priority queue. It holds at most one box from each list, and it hands you the smallest one in O(log k).

1. Put the head of every non empty list into the heap.
2. Take the smallest box out of the heap and hang it at the end of the answer.
3. If that box has a next box, put the next box into the heap.
4. Repeat until the heap is empty.

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((x, y) -> Integer.compare(x.val, y.val));
        for (ListNode head : lists) if (head != null) heap.offer(head);   // the front of each line

        ListNode dummy = new ListNode(0), tail = dummy;
        while (!heap.isEmpty()) {
            ListNode smallest = heap.poll();      // youngest front kid
            tail.next = smallest;
            tail = smallest;
            if (smallest.next != null) heap.offer(smallest.next);   // the next kid steps up
        }
        return dummy.next;
    }
}

How long it takes: each of the N boxes goes into the heap once and out once, and each heap step costs O(log k), so O(N log k). Extra room: the heap holds at most k boxes, O(k).

Another way: merge in pairs

There is a way with the same speed and no heap. Merge list 1 with list 2, list 3 with list 4, and so on. Now there are k / 2 lists. Do it again, and again, until one list is left. Like a sports tournament, each round halves the number of lists, so there are log k rounds, and each round walks all N boxes once.

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        for (int gap = 1; gap < lists.length; gap *= 2) {           // one tournament round
            for (int i = 0; i + gap < lists.length; i += 2 * gap) {
                lists[i] = mergeTwo(lists[i], lists[i + gap]);
            }
        }
        return lists[0];
    }

    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;
        return dummy.next;
    }
}

This is O(N log k) time and O(1) extra room, since it changes the lists array in place.

Watch out for

• Comparing with x.val - y.val. With very large or very negative values the subtraction overflows. Use Integer.compare.
• Putting all N boxes into the heap at once. That works but costs O(N log N) time and O(N) room. Keep only one box per list.
• Forgetting the dummy box, then special casing the very first answer box.
• Returning dummy instead of dummy.next.

What interviewers ask next

• Why is the heap log k and not log N? It never holds more than one box per list, so its size is at most k.
• Which is better, the heap or merging in pairs? Same O(N log k) time. The pairs version needs no extra room and has smaller constants. The heap version works when lists arrive as streams and you cannot see them all at once.
• What if the inputs are arrays instead of lists? Same heap, but store (value, which array, index) in it.
• Find the smallest range that has at least one number from each of k sorted lists (LeetCode 632). Same heap of front boxes, plus track the biggest front value.
• Flatten a linked list with bottom pointers. It is the same problem: every column is a sorted list to merge.

Remember this

Grown-up words: the lunch lines are sorted linked lists, the podium is a min heap or priority queue, the youngest on top is the heap's minimum, the tournament is divide and conquer, and mergeTwo is the merge step of merge sort.