Merge K Sorted Lists
The Prompt
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 its head.
Understanding the Problem
With k sorted lists, the next node of the merged output is always the smallest among the k current heads. Merging lists one-by-one works but is slow: early nodes get re-compared in every subsequent merge, giving O(N·k) total for N nodes.
A min-heap fixes the bottleneck: keep exactly the k current heads in the heap. The root is the global minimum by construction, so "pop the root, append it to the output, push its next node" repeatedly builds the merged list — each decision costs O(log k) instead of O(k).
The Interview Flow
Interviewer
How would you merge k sorted linked lists?
Candidate
A naive approach would be to merge the lists one by one. Merge list 1 and 2, then merge the result with list 3, and so on. This would be inefficient because later merges would be on very long lists.
Interviewer
What would be a more efficient approach?
Candidate
A much better way is to use a min-heap (or priority queue). I can insert the head node of each of the k lists into the min-heap. The heap will always keep the node with the smallest value at the top.
Interviewer
How do you build the final list from the heap?
Candidate
I'd extract the minimum node from the heap, add it to my result list, and then if that node has a `next` element, I'd insert that `next` element back into the heap. I repeat this process until the heap is empty. This ensures I'm always picking the globally smallest node among all lists.
Interviewer
What is the time complexity of that?
Candidate
If there are `N` total nodes and `k` lists, inserting into the heap takes O(log k). We do this for all `N` nodes. So, the total time complexity is O(N log k).
Interviewer
That's a great solution. Is there another way, perhaps without a heap?
Candidate
Yes, I can use a divide and conquer approach. I can recursively merge the lists in pairs. For example, merge list 1 with 2, 3 with 4, etc. Then take the results and merge them in pairs again, until only one list remains. This is like a merge sort on the lists.
Interviewer
That also works and has the same time complexity. Let's stick with the min-heap approach for the implementation.
Why does a heap of just k nodes suffice?
The invariant: at every moment the heap holds the earliest unconsumed node of each non-empty list, and every node already appended is ≤ everything still in the heap or behind it. Since lists are sorted, the only candidate for "next smallest overall" is one of those k front-runners — popping the heap root is provably the correct next output, and pushing its successor restores the invariant.
Every one of the N nodes is pushed and popped exactly once at O(log k) each: O(N log k) time, O(k) extra space. Compare sequential merging at O(N·k) — for k = 1000 lists that is roughly a 100× difference in comparisons. Divide-and-conquer pair merging also achieves O(N log k) with O(1) heap space, which is the strongest follow-up to mention.
Optimal Solution with a Min-Heap
- Create a min-heap (priority queue).
- Iterate through the input array of `lists`. For each non-null list head, add it to the min-heap. The priority should be based on the node's value.
- Create a `dummy` head node and a `tail` pointer for the result list.
- Loop while the min-heap is not empty.
- Extract the node with the minimum value from the heap.
- Append this node to the result list by setting `tail.next` and updating `tail`.
- If the extracted node has a `next` node, add that `next` node to the min-heap.
- After the loop, return `dummy.next`.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
// A proper MinPriorityQueue implementation would be needed for this to run.
// This is a conceptual example using a merge-pair-by-pair approach.
function mergeKLists(lists) {
if (!lists || lists.length === 0) return null;
while (lists.length > 1) {
let mergedLists = [];
for (let i = 0; i < lists.length; i += 2) {
const l1 = lists[i];
const l2 = (i + 1 < lists.length) ? lists[i+1] : null;
mergedLists.push(mergeTwoLists(l1, l2));
}
lists = mergedLists;
}
return lists[0];
}
function mergeTwoLists(l1, l2) {
const dummy = new ListNode();
let tail = dummy;
while(l1 && l2) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = l1 || l2;
return dummy.next;
}Explanation
Merge lists A = 1 → 4 → 5, B = 1 → 3 → 4, C = 2 → 6 with a size-3 min-heap.
1Seed the heap with the three heads: 1 (A), 1 (B), 2 (C). The root is the global minimum across all lists.
2Pop 1 (A) into the output and push its successor 4 (A). The heap re-settles with 1 (B) as the new root.
3Pop 1 (B), push its successor 3 (B). Output is 1 → 1; heap holds {2, 3, 4} — still one front-runner per list.
4Repeating pop-then-push until the heap empties yields 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6. All 8 nodes cost O(log 3) each.
Complexity Analysis
TIME
O(N log k)
SPACE
O(k)
Finished working through this one?
Mark it complete to track it on your Data Structures path.