Merge k Sorted Lists
Merge k sorted linked lists into one sorted list.
Pattern fit
At every step you only need the smallest current head among k lists, so the heap is exactly the right frontier structure.
Key observation
The heap never needs whole lists, only the current head of each unfinished list.
Target complexity
O(n log k) / O(k)
How to break down the solution cleanly
At every step you only need the smallest current head among k lists, so the heap is exactly the right frontier structure.
The heap never needs whole lists, only the current head of each unfinished list.
Define what the heap top represents in one sentence.
Push new candidates as soon as they become eligible.
Reference implementation
Python# Generic pattern template
import heapq
heap = []
heapq.heappush(heap, value)
smallest = heapq.heappop(heap)
# max heap in Python
heapq.heappush(heap, -value)
largest = -heapq.heappop(heap)
Common pitfalls
Trying to merge pairwise without noticing the cleaner heap abstraction.
Forgetting to push the next node after popping one head.
Common follow-ups
How does this compare with divide-and-conquer merging?
What should the heap key be if values tie?
Continue with related problems
Build repeatable depth inside the Heap / Priority Queue cluster before moving on.