Merge k Sorted Lists

The heap is only half the solution. The real insight is maintaining exactly one valid frontier node per sorted list.

The contract and the answer direction

You receive an array of k singly linked-list heads. Every non-empty list is sorted in ascending order. The result must contain every input node, including nodes with duplicate values, in one ascending linked list.

Let:

• K be the number of input lists.
• N be the total number of nodes across all lists.

The repeated task is precise:

Select the smallest currently unmerged node across all lists.

A direct solution is:

1. Put every non-null list head into a min-heap.
2. Remove the smallest node.
3. Attach that existing node to the result.
4. If it has a successor, put that successor into the heap.
5. Repeat until the heap is empty.

The output reuses the original nodes. A dummy node helps construct the result, but it is only a temporary anchor; it is not part of the merged data.

This is the core Merge k Sorted Lists solution. The rest of the problem is proving that this small loop always exposes the right candidates and implements safely under the language's comparison rules.

Recognize the k-way merge pattern

The useful signal is not merely “there are many linked lists.” It is this combination:

• There are multiple independently sorted sources.
• Each source has one current candidate.
• The next output must be the smallest candidate across those sources.
• After consuming one candidate, only that candidate's source advances.

Each list's current head is the only node from that list that can be the next output. Every later node is at least as large as its current head because the list is sorted.

That gives us a frontier:

The frontier contains one representative—the smallest unconsumed node—from every source that still has data.

A heap maintains the smallest item in that frontier without scanning every list head from scratch.

A scan-based implementation would inspect up to K heads for every output node. That costs O(K) per selection and O(NK) overall in the worst case. The heap replaces that repeated scan with insertion and removal operations costing O(log K).

This is a k-way merge heap pattern. It is related to merging sorted arrays or streams, but the linked-list version has an additional obligation: preserve node identity and advance pointers without losing links.

Do not confuse it with Top K. Top K stops after selecting a bounded number of items. Here, every source must eventually be consumed.

Compare the baseline strategies

The heap is useful because it preserves the structure already present in the input. Before choosing it, compare the alternatives.

Collect everything and sort

You could traverse every list, collect all values or nodes, sort them, and then build or reconnect a result.

That works functionally, but it discards the important fact that each input is already sorted. Collecting values uses O(N) additional storage, and rebuilding the result may also fail a contract that expects the original nodes to be reused.

It is a reasonable correctness baseline. It is not the right exploitation of the input structure.

Scan the current heads

You can keep one pointer per list and repeatedly scan all current pointers to find the smallest node.

This preserves node identity and uses little extra storage, but it performs too much selection work:

• At most K head comparisons per output node.
• N output nodes.
• O(NK) worst-case time.

The algorithm is simple. The bottleneck is visible. We are repeatedly rediscovering the minimum among almost the same candidates.

Merge lists pairwise

A second valid approach is to merge lists two at a time. If the merge schedule is balanced, each node participates in about log K merge levels, giving O(N log K) time.

The schedule matters. Merging the accumulated result with the next list sequentially can repeatedly traverse a long result and approach O(NK) in an unfavorable distribution.

Pairwise merging is a sound alternative, especially when a reusable two-list merge function is already available. But the heap follows more directly from the problem's state: one advancing candidate per source.

My decision rule is simple:

If the state naturally consists of one current item from each sorted source, use a heap to maintain the best frontier item.

Derive the frontier invariant

The algorithm becomes straightforward once the heap's meaning is explicit.

Initialization

For every non-null list head, push one heap entry.

Empty lists contribute nothing because they have no candidate. At this point, each non-empty source contributes its smallest unmerged node.

Invariant

At the start of every loop iteration:

The heap contains the smallest unmerged node from every list that still contains unmerged nodes.

Therefore, the minimum heap entry is the smallest node available globally.

This is the entire engine. The heap does not contain every unmerged node. It contains one live representative per source.

Transition

Remove the minimum node node.

• node is the next output node.
• Attach it to the result.
• Its source has now advanced.
• If node.next exists, insert that successor as the source's new representative.

Do not insert later nodes from the same list. They are blocked behind the current frontier node. Because the list is sorted, no later node can be selected before its predecessor.

A compact trace makes the movement concrete:

• A: 1 → 4 → 5
• B: 1 → 3 → 4
• C: 2 → 6

The heap state below shows (value, source) entries.

The two 1 values can be emitted in either source order. The contract requires ascending values and inclusion of every node; it does not require stability between equal-valued sources.

The heap is a small control panel for the merge. One source advances, one successor becomes visible, and the rest of the frontier remains untouched.

Prove correctness before coding

A strong interview explanation should cover more than “the heap gives the minimum.”

Initialization

For each non-empty list, the head is its smallest unmerged node. The heap contains exactly those heads. Empty lists have no unmerged node and correctly contribute no entry.

So the invariant holds before the first extraction.

Maintenance

Assume the invariant holds before an extraction. The heap minimum is removed and attached to the result.

Only its source can expose a new candidate: the successor of the removed node. Every other source's current representative remains unchanged. Inserting that successor, when present, restores one smallest unmerged representative for the advanced source.

The invariant therefore holds for the next iteration.

Sorted output

At every iteration, the heap contains the smallest unmerged node from each active source. Its minimum is therefore no greater than every remaining node's current representative, and every later node in each source is no smaller than that representative.

So the selected node is globally smallest among all unmerged nodes. Appending selections in that order produces a non-decreasing result.

Completeness and identity

Each node enters the heap when it becomes a source frontier and leaves exactly once when selected.

When a node leaves, its successor is exposed. This continues until that source is exhausted. No node is copied, skipped, or inserted twice under the normal contract that the input lists are separate linked lists.

The output attaches the existing node objects. The dummy node is the only construction helper allocated by the algorithm.

Implement the heap safely in Python

Python's heapq compares tuple entries lexicographically. If two entries have the same value, Python compares the next tuple field. A raw ListNode should not be allowed to become the tie-breaker: ordinary ListNode objects do not necessarily define an ordering.

Use the list's source index as a deterministic comparable tie-breaker:

import heapq
from typing import List, Optional


# Definition supplied by the problem:
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def mergeKLists(
        self, lists: List[Optional["ListNode"]]
    ) -> Optional["ListNode"]:
        heap = []

        # Keep one entry for each non-empty source.
        for source_index, node in enumerate(lists):
            if node is not None:
                heapq.heappush(heap, (node.val, source_index, node))

        dummy = ListNode()
        tail = dummy

        while heap:
            _, source_index, node = heapq.heappop(heap)

            # Reuse the input node instead of allocating a replacement.
            tail.next = node
            tail = node

            # Advance only the source that produced the selected node.
            if node.next is not None:
                heapq.heappush(
                    heap,
                    (node.next.val, source_index, node.next),
                )

        return dummy.next

Each state variable has one job:

• heap stores the current frontier.
• source_index identifies which list must advance after extraction.
• node is the existing input node selected for output.
• dummy removes the special case for attaching the first real node.
• tail marks the end of the result under construction.

The tuple (node.val, source_index, node) matters. The value determines sorted order. The source index resolves equal values without comparing ListNode objects.

Using the source index is safer than modifying ListNode.__lt__ globally. Changing the node class can affect unrelated code and hides the heap's ordering rule inside a shared data type. Keep comparison metadata local to this algorithm.

After attaching node, the code reads node.next and pushes that successor. It does not need to copy the node or manually sever its pointer under the normal singly linked-list contract. The final selected node is already the tail of its original chain, so its existing next is None.

Complexity, edge cases, and failure modes

Let N be the total number of nodes and K the number of input lists.

With individual heap pushes:

• Initializing the heap costs up to O(K log K).
• Every node is pushed once and popped once.
• Each heap operation costs O(log K) because the heap contains at most one entry per source.
• Processing all nodes costs O(N log K).
• Auxiliary heap space is O(K).
• The result itself does not require O(N) extra storage because the algorithm reuses the input nodes.

The combined bound is commonly written as O(N log K) for the main merge work, with the initialization included in the same practical scale when N is nonzero. More precisely, the individual-push version performs O(K log K + N log K) heap work.

Check these cases explicitly:

Common failures are diagnostic:

• Push null heads. The heap then contains invalid candidates and the code may dereference None.
• Push raw nodes. Equal values can force Python to compare unsupported ListNode objects.
• Push every node initially. This destroys the one-frontier invariant and expands heap space toward O(N).
• Lose the successor. If you overwrite pointers or move state in the wrong order, a source can disappear from the result.
• Create new nodes unnecessarily. That can violate the node-reuse expectation and adds allocation work without solving a problem.
• Claim O(N log N) automatically. The relevant heap bound is K, not N, because the heap stores at most one live candidate per list.
• Assume duplicates need special logic. They do not. The heap's tie-breaker is an implementation concern, not a change to the ordering contract.

The decision boundary is equally important: if the input sources are not individually sorted, the frontier invariant is false. A source's current head may no longer dominate its later nodes, so pushing only one representative per source cannot guarantee the global minimum.

The transferable interview move

When several sources are monotonic and the answer repeatedly needs the smallest unconsumed item, maintain one frontier candidate per source and select the next frontier with a heap.

Before writing the loop, answer three questions:

1. What source does each heap entry represent?
2. What becomes eligible when that entry is extracted?
3. What invariant says the heap contains every candidate that could be next?

For this problem, the answers are:

• Each entry represents one sorted linked list.
• Extracting a node exposes exactly its successor.
• The heap contains the smallest unmerged node from every non-empty source.

That is the durable idea. The heap is only the selection mechanism. The one-frontier-per-source invariant is what makes the mechanism valid.

When you meet an unfamiliar problem with multiple ordered inputs, identify the sources, define their frontiers, verify how one source advances, and then choose the structure that keeps the best frontier visible. Clear the noise. Find the candidates. Advance exactly one source.