Intuition
At any moment the next output node is the smallest of the k current heads. A min-heap of heads answers that in O(log k): pop the winner, append it, push its successor. Total n nodes × log k.
Merging two sorted lists is a pointer comparison; merging k of them is the same idea with a heap deciding which pointer to advance. The general pattern: when you repeatedly need the minimum across k moving frontiers, a heap of size k gives it in O(log k) instead of an O(k) scan. Only the k current heads ever need to be in memory — not the whole input.
Approach
Heap of current heads
Seed with each list's head. Ties on value need a tiebreaker (list index) since ListNodes don't compare.
Pop, append, replenish
The popped node joins the output tail; its next (if any) enters the heap. The heap never exceeds k.
Alternative: pairwise merge
Merging lists two at a time in rounds is also O(n log k) — the heap version streams and is simpler to reason about.
Solution & live demo
Common pitfalls
Putting nodes in the heap without a tiebreaker
heap = [(node.val, node) for node in lists if node]
heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
When two nodes share a value, Python falls through to comparing the second tuple element — and ListNode defines no <, so it raises TypeError. The list index is unique, so it settles ties before any node comparison happens.
Pushing every node upfront
heap = [(n.val, i, n) for i, l in enumerate(lists)
for n in iterate(l)]heap = [(node.val, i, node) for i, node in enumerate(lists) if node] # push each successor only as its predecessor is popped
That's O(N) space for N total nodes and turns each operation into O(log N). Holding only the k list heads keeps the heap at size k, so space is O(k) and each push is O(log k).
Returning dummy instead of dummy.next
return dummy
return dummy.next
dummy is a placeholder node holding value 0 that exists only so tail has something to attach to on the first iteration. It is not part of the answer — the real head is whatever got linked after it.
Edge cases
Empty lists never enter the heap; all-empty returns None.
The (val, idx) tuple breaks ties deterministically.