02
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.
03
Approach
1
Heap of current heads
Seed with each list's head. Ties on value need a tiebreaker (list index) since ListNodes don't compare.
2
Pop, append, replenish
The popped node joins the output tail; its next (if any) enters the heap. The heap never exceeds k.
3
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.
04
Solution & live demo
python
▶1import heapq
▶2
▶3class Solution:
▶4 def mergeKLists(self, lists):
▶5 heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
▶6 heapq.heapify(heap)
▶7 dummy = tail = ListNode(0)
▶8 while heap:
▶9 val, i, node = heapq.heappop(heap)
▶10 tail.next = node
▶11 tail = node
▶12 if node.next:
▶13 heapq.heappush(heap, (node.next.val, i, node.next))
▶14 return dummy.next
05
Edge cases
Some lists empty / all empty
Empty lists never enter the heap; all-empty returns None.
Equal values across lists
The (val, idx) tuple breaks ties deterministically.
06
Complexity
Time
O(n log k)
Space
O(k)
n total nodes; heap holds one node per list.