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.
TimeO(n log k)SpaceO(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.