Merge k Sorted Lists
Problem Statement
You are given an array lists containing the heads of k sorted linked lists. Merge all nodes into one sorted linked list and return the head of the merged list. The merge should reuse existing nodes by rewiring next pointers rather than copying values into a new data structure.
Input
An array lists where each entry is the head pointer of a sorted singly linked list. Empty lists may appear as null entries.
Output
The head pointer of one sorted linked list containing every node from every input list.
Constraints
- •
k == lists.length - •
0 <= k <= 10^4 - •
0 <= lists[i].length <= 500 - •
-10^4 <= Node.val <= 10^4 - •
lists[i] is sorted in non-decreasing order - •
The total number of nodes across all lists is at most 10^4
Examples
Example 1
lists = [[1,4,5],[1,3,4],[2,6]]
[1,1,2,3,4,4,5,6]Example 2
lists = []
[]Example 3
lists = [[]]
[]Learning Objectives
- Recognise the k-way merge signal: multiple sorted sequences where the next answer is always one of the current heads.
- Use a min-heap of at most **k** list heads to avoid scanning all lists for every output node.
- Maintain a dummy tail so linked-list output construction has no first-node special case.
- Explain the O(N log k) bound from polling and pushing each node through a heap of size **k**.
Intuition
Pattern Recognition
The signal is k sorted linked lists or merge many sorted streams. In a normal two-list merge, the next output node must be one of the two heads. With k lists, the same idea still holds: the next output node must be the smallest among the k current heads.
The trap is scanning all heads for every node. If there are N total nodes, a repeated scan costs O(Nk). A min-heap keeps only the current head of each non-empty list, so finding the smallest head costs O(log k). After that node is appended, only its own list advances, so only that node next pointer needs to be pushed into the heap.
Common mistakes
- ×Putting every node into the heap at once, which works but wastes space and misses the streaming k-way merge pattern.
- ×Forgetting to push the next node from the same list after polling its current head.
- ×Building new nodes unnecessarily instead of splicing the original linked-list nodes into the output.
- ×Returning the dummy node itself instead of **dummy.next**.
Algorithm Explanation
Key idea
Use a min-heap ordered by node value. The heap contains at most one active node from each list: the current unmerged head. The heap root is therefore the globally smallest node that can legally come next. Poll it, attach it after the output tail, then push its successor from the same list.
Heap walkthrough
For lists = [[1,4,5],[1,3,4],[2,6]], start by pushing the first node of each list. The heap is [1 from list 0, 1 from list 1, 2 from list 2]. Poll 1 from list 0, append it, and push its next node 4 from list 0. The heap becomes [1 from list 1, 2 from list 2, 4 from list 0].
Next poll 1 from list 1 and push 3 from list 1, so the heap becomes [2 from list 2, 3 from list 1, 4 from list 0]. Poll 2 from list 2 and push 6 from list 2, giving [3 from list 1, 4 from list 0, 6 from list 2]. The same rule continues until the heap is empty. The output tail has received nodes in sorted order: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6.
Algorithm
- Create a min-heap ordered by node.val.
- Push the head of every non-empty list into the heap.
- Create a dummy node and keep tail at the end of the merged output.
- While the heap is not empty, poll the smallest node.
- Attach that node after tail and advance tail.
- If the polled node has a next node, push that next node into the heap.
- Return dummy.next.
A divide-and-conquer pairwise merge is another optimal O(N log k) approach, but the heap version is the canonical streaming k-way merge template.
Solutions
Solution: Min-heap k-way merge
Use this as the default interview solution when the input is already split into sorted streams and you need to repeatedly emit the smallest current head.
Keep one candidate from each non-empty list in a min-heap. Each poll gives the next output node. Since only the source list of that node changed, push only that node successor back into the heap.
Step-by-step
- Create a PriorityQueue that compares list nodes by value.
- Offer every non-null list head into the heap.
- Attach polled nodes behind a dummy output node using a moving tail pointer.
- After attaching a node, offer its next node if it exists.
- Continue until the heap is empty, then return dummy.next.
O(N log k)
O(k)
Each of the N nodes is polled once, and at most one node per list is stored in the heap.
Java implementation
Dry Run
Sample input
lists = [[1,4,5],[1,3,4],[2,6]]. The heap stores only the current head from each non-empty list.
| step | polled node | heap after push | merged output |
|---|---|---|---|
| start | none | [1 from L0, 1 from L1, 2 from L2] | empty |
| 1 | 1 from L0 | [1 from L1, 2 from L2, 4 from L0] | 1 |
| 2 | 1 from L1 | [2 from L2, 3 from L1, 4 from L0] | 1 -> 1 |
| 3 | 2 from L2 | [3 from L1, 4 from L0, 6 from L2] | 1 -> 1 -> 2 |
| 4 | 3 from L1 | [4 from L0, 4 from L1, 6 from L2] | 1 -> 1 -> 2 -> 3 |
| 5 | 4 from L0 | [4 from L1, 5 from L0, 6 from L2] | 1 -> 1 -> 2 -> 3 -> 4 |
| 6 | 4 from L1 | [5 from L0, 6 from L2] | 1 -> 1 -> 2 -> 3 -> 4 -> 4 |
| 7 | 5 from L0 | [6 from L2] | 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 |
| 8 | 6 from L2 | [] | 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 |
Every row removes exactly one node from the heap and appends it to the output. Because the heap always contains the smallest unmerged head from each list, the merged output remains sorted.
Interview Tips
Say the invariant clearly: the heap contains the smallest unmerged node from each list that still has nodes. That invariant proves both correctness and the O(k) space bound. If the interviewer asks for alternatives, mention divide-and-conquer pairwise merging, which also reaches O(N log k) time but uses recursive merge structure instead of a heap.
Likely follow-ups
- How would you solve the same problem with divide-and-conquer pairwise merging?
- What changes if the input streams arrive lazily and cannot all be loaded at once?
- How would you make the merge stable when equal values appear across different lists?
- How would you merge k sorted arrays instead of linked lists?
Similar Problems
Key Takeaways
- For k sorted streams, the next global element must be the smallest current stream head.
- A min-heap reduces repeated head selection from O(k) per node to O(log k) per node.
- After polling a node, only that node successor can become a new candidate.
- A dummy tail keeps linked-list construction simple and avoids first-node edge cases.