Why it works
- Each list is sorted, so the smallest node not yet linked is always the first unused node of some list. The heap holds exactly those, one per list, so its top is the next node of the answer.
- An empty list has no head and never enters the heap; a list that runs out pushes nothing, and the heap just gets smaller. Neither needs a special case later.
- The dummy node lets the first node be linked like every other one, so tail.next = node is the same line every time; the nodes are relinked, never copied.
Complexity
Time O(N log k) for N nodes in k lists: each node is pushed and popped once on a heap of at most k. Memory O(k) for the heap: the answer reuses the nodes.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗