Merge k Sorted Lists
Problem Statement
You are given an array of k linked lists, where each linked list is sorted in ascending order. Merge all the lists into one sorted linked list and return its head.
Input
An array lists of linked-list heads, where each individual list is already sorted.
Output
The head of one sorted linked list containing every node from every input list.
Constraints
- •
0 <= k <= 10^4 - •
0 <= lists[i].length <= 500 - •
-10^4 <= lists[i][j] <= 10^4 - •
Each linked list is sorted in ascending 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 -> 6Example 2
lists = []
[]Example 3
lists = [[]]
[]Learning Objectives
- Recognise **k sorted streams** as a current-head selection problem.
- Reuse the merge-two-sorted-lists building block without creating new list nodes.
- Compare the min-heap strategy with divide-and-conquer pairwise merging.
- Maintain a clean output tail while preserving every remaining next pointer until its node is processed.
Intuition
Pattern Recognition
The signal is many already-sorted linked lists. If there were only two lists, you would use the standard merge-two-sorted-lists pointer template. With k lists, the same idea still applies: the next output node must be the smallest among the current heads of all non-empty lists.
Scanning all k heads for every output node is wasteful. A min-heap stores only the live candidates, one current head per list, so selecting the next node costs O(log k) instead of O(k). After removing a node from the heap, push its successor because that successor becomes the new head of that same sorted stream.
A second interview-ready recognition is divide and conquer: repeatedly merge lists in pairs, just like the merge phase of merge sort. This reuses the two-list merge building block and gives the same O(N log k) total time while avoiding heap operations.
Common mistakes
- ×Pushing every node into the heap at once instead of only the current heads, which uses unnecessary memory.
- ×Forgetting to push the polled node's successor, which drops the rest of that list.
- ×Creating new nodes and losing the original node identities when the problem only needs pointer rewiring.
- ×Not handling **k = 0** or all-empty lists before returning the final head.
Algorithm Explanation
Key idea
Keep one candidate per list. The heap always contains the smallest unmerged node from each list that still has nodes. Polling the heap chooses the globally smallest next node, appending it advances the output tail, and pushing its successor restores the invariant for that list.
Pointer walkthrough
Use A: 1 -> 4 -> 5, B: 1 -> 3 -> 4, and C: 2 -> 6. Start with heap heads A1, B1, C2 and output dummy. Poll A1, append it, and push A4; the output is dummy -> 1 and the heap is B1, C2, A4. Poll B1, append it, and push B3; the output is dummy -> 1 -> 1 and the heap is C2, B3, A4. Poll C2, append it, and push C6. Continue polling B3, A4, B4, A5, and C6 until the heap is empty. The output tail always points to the last appended node, and the heap contains the next possible heads.
Algorithm
- Create a min-heap ordered by node value.
- Push every non-null list head into the heap.
- Create a dummy head and keep tail at the end of the merged output.
- While the heap is not empty, poll the smallest node.
- Append that node after tail and move tail forward.
- If the appended node has a next node, push that successor into the heap.
- After the loop, terminate tail.next and return dummy.next.
Solutions
Solution 1: Min-heap of current heads
Use this as the primary interview solution when k sorted lists arrive independently and you want the clearest pick the next smallest head invariant.
Store only the current head of each non-empty list in a min-heap. Each poll appends one node to the answer, and that node's successor becomes the new candidate from the same list.
Step-by-step
- Build a PriorityQueue ordered by node value.
- Offer each non-null input head to seed the heap with at most k candidates.
- Use dummy and tail to build the merged list without special-casing the first node.
- Poll the smallest node, append it after tail, and advance tail.
- If the polled node has a successor, offer that successor to the heap.
- Set tail.next to null after all nodes are appended and return dummy.next.
O(N log k)
O(k)
**N** total nodes are polled once, and the heap holds at most one node per list.
Java implementation
Solution 2: Divide and conquer pairwise merge
Use this when you want to emphasise reuse of the two-list merge primitive and avoid an explicit heap.
Repeatedly merge lists in pairs: merge list 0 with 1, 2 with 3, then double the interval and merge the merged runs. Each node participates in one merge per level.
Step-by-step
- If the input array is empty, return null.
- Start with interval = 1, meaning adjacent lists are paired.
- For each pair i and i + interval, merge them with the standard two-list dummy-tail routine and store the result at lists[i].
- Double interval so the next pass merges groups twice as large.
- Continue until interval reaches the number of lists.
- Return lists[0], the fully merged list.
O(N log k)
O(1)
There are O(log k) merge levels, and every level touches each node once; the input array stores merged heads.
Java implementation
Dry Run
Sample input
lists = [[1 -> 4 -> 5], [1 -> 3 -> 4], [2 -> 6]]. Track the heap of current heads and the merged output after each poll.
| step | heap heads before poll | node appended | new head pushed | merged list |
|---|---|---|---|---|
| seed | A1, B1, C2 | none | A1, B1, C2 | dummy |
| 1 | A1, B1, C2 | A1 | A4 | 1 |
| 2 | B1, C2, A4 | B1 | B3 | 1 -> 1 |
| 3 | C2, B3, A4 | C2 | C6 | 1 -> 1 -> 2 |
| 4 | B3, A4, C6 | B3 | B4 | 1 -> 1 -> 2 -> 3 |
| 5 | A4, B4, C6 | A4 | A5 | 1 -> 1 -> 2 -> 3 -> 4 |
| 6 | B4, A5, C6 | B4 | none | 1 -> 1 -> 2 -> 3 -> 4 -> 4 |
| 7 | A5, C6 | A5 | none | 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 |
| 8 | C6 | C6 | none | 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 |
Every row appends the smallest current head and then advances only that source list. When the heap becomes empty, the merged list contains all 8 nodes in sorted order.
Interview Tips
Lead with the two-list merge intuition, then explain why k lists need a data structure to choose the next smallest head efficiently. Name N as the total node count and k as the number of lists; interviewers expect that distinction. If asked for alternatives, describe pairwise merging as merge sort over lists: it is not brute force, it is the same merge primitive applied in balanced levels.
Likely follow-ups
- How would the solution change if the lists arrived as an iterator stream instead of an array?
- What if you needed to preserve the original lists and could not relink their nodes?
- How would you merge **k** sorted arrays, and what changes compared with linked lists?
- When would divide-and-conquer merging be preferable to a heap in production?
Similar Problems
Key Takeaways
- For **k** sorted lists, the next output node is the smallest among the current heads.
- A min-heap reduces repeated head selection from **O(k)** to **O(log k)** per node.
- Divide-and-conquer pairwise merging is the natural alternative and reuses Merge Two Sorted Lists.
- The output tail should relink existing nodes and finish with a clean **null** tail.