Merge k Sorted Lists

Merge k Sorted Lists takes the classic "merge two sorted lists" and scales it up. The trick that makes it fast is a min-heap — a structure that always hands you the smallest item it holds in O(log k).

The slow way first

The obvious idea: dump every node into one array, sort it, and rebuild a list. With n total nodes that is O(n log n) and ignores the fact that each list is already sorted.

A cleaner thought: merge them two at a time, like a tournament. But naively merging list 1 with list 2, then that result with list 3, and so on, re-walks the growing merged list over and over — that drifts toward O(n · k). We want something that exploits the sorted-ness directly.

The idea: a heap of the current heads

At any moment, the next node in the merged output is the smallest among the current heads of the still-nonempty lists. There are only k heads to compare. A min-heap keeps those k candidates ordered so we can pop the smallest in O(log k) and push the popped node's successor in O(log k).

The key insight: we never compare more than k items at once, and every node enters and leaves the heap exactly once.

Walk through it

Step through the animation. We seed the heap with all three heads (1, 1, 2). Each round pops the heap minimum into the output row, then pushes that node's next back into the heap. When a list runs out there is nothing to push, so the heap shrinks. The output row builds up in perfect sorted order: 1, 1, 2, 3, 4, 5, 6, 8.

Pseudocode

make an empty min-heap ordered by node value
for each list:
    if it is nonempty, push its head into the heap
create a dummy head for the output, tail = dummy
while the heap is not empty:
    pop the node with the smallest value
    append it to the output (tail.next = node, tail = node)
    if the popped node has a next:
        push node.next into the heap
return dummy.next

The Python solution

import heapq
 
def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    out = dummy = ListNode()
    while heap:
        val, i, node = heapq.heappop(heap)
        out.next = node
        out = out.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

• We seed the heap with the head of every nonempty list. Each entry is a tuple (node.val, i, node).
• The middle i is a tie-breaker: when two nodes share a value, Python compares the next tuple element. Using the list index i keeps it from ever trying to compare two ListNode objects (which have no ordering).
• out = dummy = ListNode() builds the result behind a dummy head so we avoid special-casing the first node.
• Each loop pops the smallest, links it onto the output, and advances out.
• Only if the popped node has a next do we push it — that is how an exhausted list quietly leaves the heap.

Complexity

The heap never holds more than k nodes at once, so it costs O(k) extra space. Every one of the n nodes is pushed and popped exactly once, and each heap operation is O(log k): O(n log k) total — better than O(n log n) whenever k < n.

When this pattern shows up

Practice