Heaps & Priority Queues Pattern

Merge K Sorted Lists

You are given an array of k linked-list heads, each list already sorted in ascending order. Merge them all into a single ascending list and return its head.

The array itself may be empty, and any individual head may be null, so both must be handled. Duplicate values across lists are kept — nothing is deduplicated. You are free to reuse the existing nodes by rewiring their next pointers rather than allocating new ones.

CONSTRAINTS

0 <= k <= 10⁴
0 <= lists[i].length <= 500
-10⁴ <= lists[i][j] <= 10⁴
Every input list is sorted in ascending order.
Total nodes N across all lists: 0 <= N <= 10⁴

EXAMPLE 1

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

Output: [1,1,2,3,4,4,5,6]

All eight values arranged in ascending order. Both 1s survive and both 4s survive, since duplicates coming from different lists are separate nodes.

EXAMPLE 2

Input: lists = []

Output: []

There are no lists at all, so there is nothing to merge and the result is empty. This is distinct from being given lists that happen to be empty.

EXAMPLE 3

Input: lists = [[],[1]]

Output: [1]

The first list contributes no nodes. A null head is a valid list, not an error, so it is simply skipped and the surviving single node is the whole answer.

EXAMPLE 4

Input: lists = [[-3,-1],[-2,-1]]

Output: [-3,-2,-1,-1]

Negative values sort like any others, with -3 smallest. The two -1s come from different lists and both appear in the output.

Can the outer array be empty, or contain null heads?

Both. An empty array returns null, and individual null heads must be skipped rather than dereferenced. These two cases account for most failed submissions on this problem, so handle them before anything else.

May I reuse the input nodes, or must I allocate a new list?

Reuse is allowed and preferred — rewiring next pointers means O(1) extra memory for the output. Confirm the caller does not need the original lists intact, because rewiring destroys them.

Are duplicate values kept, and can values be negative?

Duplicates are all kept, including duplicates within a single list, and values range down to -10⁴. Nothing about the merge depends on sign.

Is every input list guaranteed to be sorted, or should I verify?

It is guaranteed, and that guarantee is load-bearing — every efficient approach relies on it. If an interviewer said the lists might be unsorted, no merge-based technique applies and you would be back to collecting and sorting everything.

Before any algorithm, notice what "each list is already sorted" actually buys you. In a sorted list, the smallest remaining value is always the head — never buried in the middle. So across k sorted lists, the smallest unused value in the entire input is always one of the k current heads. Never anywhere else.

That reduces a search over N nodes to a search over k candidates, and it is the fact everything below is built on.

Approach one: throw the structure away

You could ignore the sortedness completely — dump every value into an array, sort it, rebuild a list.

python

def merge_k_lists(lists):
    values = []
    for head in lists:
        while head:
            values.append(head.val)
            head = head.next
    values.sort()                       # O(N log N)
    dummy = tail = ListNode(0)
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

O(N log N) time and O(N) extra memory, and it works. But it is the answer to a harder problem than the one asked. Sorting exists to discover order in arbitrary data; here the order was handed to us k lists at a time and we deliberately destroyed it, only to pay to rebuild it. Any interviewer will accept this as a warm-up and then ask you to use the sortedness.

Approach two: merge them one at a time, and count the cost carefully

Merging two sorted lists is a well-known building block: walk both with a pointer each, repeatedly attaching whichever head is smaller, and when one runs out attach the rest of the other. It is O(a + b) and uses no extra memory.

So chain it — merge list 0 with list 1, merge that result with list 2, and so on.

python

def merge_k_lists(lists):
    result = None
    for head in lists:
        result = merge_two(result, head)     # each pass walks all of result again
    return result

Correct, but count what it costs. Say every list holds N/k nodes. The first merge touches 2N/k nodes, the second 3N/k, the third 4N/k. The accumulated result is re-traversed on every single step, so the total is N/k × (2 + 3 + … + k), which is about N × k / 2 — that is O(N × k). With k = 10⁴ that is catastrophic.

The waste has a precise shape: the nodes merged in the very first round get walked past k-1 more times, contributing nothing new each time. Early results are being re-read over and over.

Approach three: keep a frontier of k candidates

Return to the opening observation. At any moment, exactly k nodes are candidates for "next smallest" — one per list. Call that set the frontier. The algorithm is then obvious: take the minimum of the frontier, append it to the output, and replace it with its successor from the same list, since that successor is now that list's smallest unused value.

Doing this by scanning all k candidates each time costs O(k) per node and O(N × k) overall — no better than chaining. But "repeatedly give me the minimum of a changing set" is precisely what a min-heap is for, and here the heap is used in a third distinct way. In Kth Largest it was a bounded filter that permanently discarded losers; in Task Scheduler it was a queue whose priorities changed; here it is a frontier over k sorted sequences, holding exactly one representative per source at all times.

python

import heapq

def merge_k_lists(lists):
    heap = []
    for i, head in enumerate(lists):
        if head:                                  # skip null heads
            heapq.heappush(heap, (head.val, i, head))

    dummy = tail = ListNode(0)
    while heap:
        val, i, node = heapq.heappop(heap)        # global minimum
        tail.next = node                          # reuse the node itself
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    tail.next = None
    return dummy.next

Crucial Notethe list index i in the middle of the tuple is not decoration. When two nodes hold equal values, the heap compares the next tuple component to break the tie — and if that component were the node object, Python would raise a TypeError because ListNode has no ordering defined. Since list indices are unique, the comparison always resolves at i and never reaches the node. Duplicate values across lists are guaranteed by the constraints, so this is not a rare edge case; it fires on the very first example.

The dummy node is the other standard trick. Without it, the first node appended is a special case, because there is no previous node whose next pointer to set. Starting from a throwaway head removes that branch entirely, and the real answer is whatever dummy.next ends up pointing at.

Cost: each of the N nodes is pushed once and popped once, and the heap never holds more than k entries, so it is O(N log k) time with O(k) extra memory. Compared with the chained merge, k has moved from a multiplier into a logarithm — for k = 10⁴ that is a factor of roughly 10⁴ versus 14.

Worked example:[[1,4,5],[1,3,4],[2,6]]

The heap is shown as the set of candidate values with the list each came from.

- Seed with the three heads: {1 from L0, 1 from L1, 2 from L2}.

- Pop 1 from L0 — it ties with L1's 1, and the list index decides which leaves first. Output 1. Its successor 4 joins: {1 from L1, 2 from L2, 4 from L0}.

- Pop 1 from L1. Output 1, 1. Push 3: {2 from L2, 3 from L1, 4 from L0}.

- Pop 2 from L2. Output 1, 1, 2. Push 6: {3, 4, 6}.

- Pop 3 from L1. Output 1, 1, 2, 3. Push 4 from L1: {4 from L0, 4 from L1, 6}.

- Pop 4 from L0. Output 1, 1, 2, 3, 4. Push 5: {4 from L1, 5, 6}.

- Pop 4 from L1 — it has no successor, so nothing is pushed and L1 drops out of the frontier permanently: {5, 6}.

- Pop 5, push nothing. Pop 6, push nothing. The heap empties.

Result 1, 1, 2, 3, 4, 4, 5, 6. The heap held at most three entries throughout, even though eight nodes flowed through it — the memory tracks the number of lists, not the number of nodes.

A second optimal route: merge in pairs

There is a way to reach O(N log k) with no heap at all, and it is worth having because it needs no extra data structure. The chained merge was slow because the growing result was re-walked k times. So instead of merging into one accumulator, merge lists in pairs: list 0 with 1, list 2 with 3, and so on. That halves the number of lists, and every node is touched exactly once in the round. Repeat on the survivors.

Each round is O(N), and halving k means log₂ k rounds, giving O(N log k) — the same bound, reached by making each node be walked log k times instead of walking the whole accumulation k times. It uses O(1) extra memory if you merge iteratively.

Which to choose? Pairwise merging is often slightly faster in practice and lighter on memory. The heap wins when the lists are not all available up front — genuine streams, or k so large that holding every list is itself the problem — because it only ever needs one node per source in memory at a time. That is not a hypothetical: merging sorted runs off disk is how external sorting works, and it is the heap version that runs in production.

The takeaway

The reusable idea is the frontier. Whenever you have k sorted sources and want their combined order, you never need more than one element from each source in play at a time, and a min-heap over those k candidates produces the merged order in O(N log k). The same shape appears in the k-th smallest element of a sorted matrix — each row is a sorted list — in merging time-series streams, and in the merge phase of external sort.

Train the reflex: when the input is already partially ordered, sorting from scratch is almost always the wrong move. Ask instead where the next answer can possibly come from. If the answer is "one of a small set of frontier candidates", put that set in a heap.

Interactive Strategy Visualization