Merge K Sorted Lists
HardHeap of list heads picks the next node
Always grab the smallest current head among all the lists using a little smallest-on-top pile.
The idea
Put the head of every list into a min-heap. Repeatedly pop the smallest head, append it to the result, and push its successor. Always O(log k) to find the next node.
1
1
2
heap{1, 1, 2}
Step 1 of 10. Merge 3 sorted lists. A min-heap holds the current head of each list. heap {1, 1, 2}.
1/10
Optimal
timeO(N log k)spaceO(k)
k-way merge.
1const h = new MinHeap(byVal);2for (const node of lists) if (node) h.push(node);3while (h.size()) {4 const n = h.pop();5 tail = tail.next = n;6 if (n.next) h.push(n.next);7}Input
- list
- [1, 1, 2]
Memory
- heap
- {1, 1, 2}
Output
- merged
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- lists = [[1,4,5],[1,3,4],[2,6]]
- Output:
- [1, 1, 2, 3, 4, 4, 5, 6]
- Explanation:
- Merge all into one sorted list.
Example 2
- Input:
- lists = [[]]
- Output:
- []
- Explanation:
- Empty input → empty list.
Example 3
- Input:
- lists = [[5],[1],[3]]
- Output:
- [1, 3, 5]
- Explanation:
- Three singletons sort to 1,3,5.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.