Merge K Sorted Lists

Concept

LeetCode #23.
Problem: You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Input: lists = [[1,4,5], [1,3,4], [2,6]]
Output: [1,1,2,3,4,4,5,6]

In “Merge Two Sorted Lists”, you just put a pointer at the head of List A, and a pointer at the head of List B. You compare the two pointers, pick the smaller one, and move it forward.
If you have K lists (e.g., 100 lists), you can’t just write 100 if/else statements to compare 100 pointers.

The Min-Heap Approach ($O(N \log K)$)

How do you instantly find the absolute minimum value across 100 different lists without scanning them all one by one?
You throw the heads of all 100 lists into a Min-Heap (Priority Queue)!

1. Loop through the array of Lists. Push the Head Node of every list into the Min-Heap.
2. The Min-Heap will instantly bubble the absolute smallest Node to the very top.
3. Pop the top Node off the heap. Add it to our final merged list.
4. The Trick: If the Node we just popped has a next node attached to it, we push that next node back into the Min-Heap!
5. Repeat until the heap is empty.

Every time we push/pop from the heap, it takes $O(\log K)$ time (where $K$ is the number of lists). We do this for every single Node ($N$), resulting in $O(N \log K)$ time.

Note: JavaScript does not have a built-in Min-Heap. In an interview, you must verbally explain this optimal approach, but usually, the interviewer will accept the alternative “Divide and Conquer” approach below, which is exactly as fast but doesn’t require importing external heap libraries.

The Divide and Conquer Approach ($O(N \log K)$)

Instead of a Heap, we use the exact same logic as Merge Sort!

If we have 8 lists:

1. Merge List 1 & 2. Merge List 3 & 4. Merge List 5 & 6. Merge List 7 & 8. (We now have 4 lists).
2. Merge List 1 & 2. Merge List 3 & 4. (We now have 2 lists).
3. Merge List 1 & 2. (We now have 1 final merged list!).

We just repeatedly call the standard “Merge Two Sorted Lists” helper function in pairs! Because we are halving the total number of lists on every pass, it takes exactly $O(\log K)$ passes!

Implementation (Divide and Conquer)

// Standard Helper Function: Merges TWO lists in O(N) time.
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const dummy = new ListNode(0);
    let current = dummy;

    while (l1 !== null && l2 !== null) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    // Attach whatever is left!
    if (l1 !== null) current.next = l1;
    if (l2 !== null) current.next = l2;

    return dummy.next;
}

// Time Complexity: O(N log K)
// Space Complexity: O(1) (We merge in place!)

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    if (lists.length === 0) return null;

    // Loop until exactly 1 list remains!
    while (lists.length > 1) {
        const mergedLists: Array<ListNode | null> = [];

        // Step by 2! Grab pairs of lists!
        for (let i = 0; i < lists.length; i += 2) {
            const list1 = lists[i];
            // Handle odd-number of lists (the last list won't have a pair!)
            const list2 = (i + 1 < lists.length) ? lists[i + 1] : null;

            // Merge the pair and save it to the next round!
            mergedLists.push(mergeTwoLists(list1, list2));
        }

        // Replace the main array with our newly halved array!
        lists = mergedLists;
    }

    // The lone survivor is the final merged list!
    return lists[0];
}

Interview Questions

Q: A developer creates a massive array, loops through all K linked lists, pushes every single value into the array, runs Array.sort(), and builds a brand new Linked List from the array. Is this acceptable?
A: This is the Brute Force approach. It takes $O(N \log N)$ time (because of the massive sorting operation) and $O(N)$ Space to hold the array. While functionally correct, it completely ignores the fact that the input lists are already sorted. The Divide & Conquer approach ($O(N \log K)$ Time, $O(1)$ Space) is vastly mathematically superior because $K$ (number of lists) is drastically smaller than $N$ (total number of nodes).

Q: In the Divide and Conquer approach, why do we merge in pairs (1+2, 3+4) instead of just merging List 1 into List 2, then merging that into List 3, then List 4?
A: Merging sequentially is a fatal mistake! If you merge List 1 into List 2, the resulting list is size 2X. If you merge that into List 3, you are physically re-traversing the exact same 2X nodes again. By List 100, you are re-traversing 99X nodes just to add one tiny list. This degrades the time complexity back to an abysmal $O(N \times K)$. Merging in pairs (Divide & Conquer) perfectly balances the tree, ensuring no node is physically traversed more than $\log K$ times.