Merge k Sorted Lists
Only the k current heads can be next — keep exactly those in a min-heap.
Approach
Push the head of every list into a min-heap. Pop the smallest, append it to the output, then push that node's successor. Each of the n nodes enters and leaves the heap once, so the whole merge is O(n log k). Pairwise divide-and-conquer merging reaches the same bound without a heap.
Time complexity
O(n log k)
Space complexity
O(k)
Common mistake
Collecting every value and sorting (O(n log n)), or rescanning all k heads on each step (O(n·k)) instead of letting the heap track the minimum.
See it run, step by step
Generate an interactive lesson for Merge k Sorted Lists — trace every variable and watch the algorithm execute until it clicks.
Create a lesson with this problem