Merge K Sorted Lists: The Heap of Heads

This one is a Hard-rated classic reported from Amazon, Meta, Google interviews: "Merge k Sorted Lists". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Top-K and Heaps pattern on sight. Part 10 of 11 in the Top-K and Heaps arc.

The Problem

Merge k sorted linked lists into one sorted list. A top-five question by reported frequency for over a decade — and the canonical k-way merge, the primitive under external sorting, log-structured storage compaction, and stream joins, which is why it refuses to die.

Input:  lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]

Recognizing the Top-K and Heaps Pattern

When a problem asks for the k largest, smallest, closest, or most frequent — or for repeated access to an extreme while data changes — a heap gives O(log n) insertion and O(1) access to the extreme. The signature trick: keep a bounded heap of size k with the opposite polarity (a min-heap to track the k largest), evicting the root on overflow. Python's heapq is a min-heap; negate values for max behavior.

The next output element is always the minimum among k current heads — repeated min over a changing k-sized set, the heap's defining job. Pairwise sequential merging costs O(n·k); the heap (or divide-and-conquer pairing) brings it to O(n log k), and that gap is the whole interview.

The Approach

Push each non-empty head as (val, idx, node) — the list index breaks ties, because heapq falls back to comparing tuple fields and ListNode does not support comparison. Pop the min, splice it onto a dummy-headed tail, push the popped node's successor.

Divide-and-conquer (merge lists pairwise, halving rounds) achieves the same O(n log k) with O(1) extra space and is the better answer if the interviewer bans the heap — carry both.

Python Solution

import heapq


class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None):
        self.val = val
        self.next = next


def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
    """Merge k sorted linked lists via a heap of current heads."""
    heap: list[tuple[int, int, ListNode]] = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode()
    tail = dummy
    while heap:
        _, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

Complexity

• Time: O(n log k) — each of n nodes passes through a k-sized heap once
• Space: O(k) — the heap of heads (output reuses existing nodes)

Interview Tips and Follow-Ups

• The (val, idx, node) tie-break tuple is the Python-specific trap — equal vals fall through to comparing nodes and crash without the index. Know it cold.
• Sketch the divide-and-conquer alternative and its recurrence (n per round, log k rounds) — asked for at Google routinely.
• This is external merge sort's inner loop — one sentence connecting it to sorting 100GB with 1GB of RAM upgrades the conversation to systems.

That wraps part 10 of the Top-K and Heaps arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.