visual walkthrough
Merge k Sorted Lists
Heap-based or divide-and-conquer merging; a classic Hard.
The idea
With two lists you compare two fronts. With k lists you need the smallest of k fronts at every step, which a min-heap gives in O(log k).
Merging lists into the result one by one also works, but nodes merged early get walked again with every later list.
Complexity
| approach | time | space |
|---|---|---|
| Merge one at a time | O(k × N) | O(1) |
| Min-heap of fronts | O(N log k) | O(k) |