Merge k Sorted Lists

Combine k sorted linked lists into one, using a heap to pick the next smallest head in log k time

HardHeap· k-way merge

Linked ListHeapDivide and ConquerMerge Sort

Problem Statement

You are given an array of k linked lists, each already sorted in ascending order. Merge them into one sorted list and return its head.

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

Input:  lists = []
Output: []

Input:  lists = [[]]
Output: []

Intuition

Start from what you already know. Merge Two Sorted Lists works by comparing two heads and taking the smaller one. The natural extension is to compare all k heads and take the smallest.

That works, and it is worth writing down because it shows exactly where the cost goes:

Total nodes = N.  For each of the N outputs, scan all k heads.
Cost = O(N · k)

With k = 10,000 lists, you scan 10,000 heads to produce one node. That is the waste.

The key insight

Between one output and the next, almost nothing changes. You removed one head and replaced it with one successor. The other k - 1 heads are exactly as they were.

Rescanning all k throws away everything you learned last step. What you need is a container that maintains "which is smallest" as items come and go — and that is precisely a heap.

Swapping the scan for a heap turns each step from O(k) into O(log k).

The real-world version

Picture k queues of people, each queue already sorted by height. You want one line, shortest first.

The slow way: walk down all k queue fronts every single time you pick someone.

The heap way: keep the k queue fronts on a small sorted shelf. Take the shortest, and immediately put that queue's next person on the shelf. The shelf never holds more than k people, and finding the shortest on it is instant.

Approach

Push the head of every non-empty list

The heap starts with at most k nodes — one per list. Skip empty lists entirely.

Pop the smallest head

That node is guaranteed to be the next value in the merged output. No other list can hold anything smaller, because every list is sorted and this was the smallest of all the fronts.

Append it, then push its successor

If the popped node has a next, push that in. This keeps the invariant: the heap always holds the current front of every list that still has nodes.

Repeat until the heap is empty

Use a dummy head so appending never needs a special case for the first node.

Watch it run

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

Queue (front → back)

1(a)

1(b)

2(c)

output—

Seed the heap with all three heads. The smallest is 1, from list a.

1 / 7

The heap holds at most k nodes at any moment, regardless of how long the lists are.

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 using a min-heap of the current heads."""
    # (value, tiebreaker, node). The tiebreaker matters: when two values are
    # equal, Python compares the NEXT tuple element, and ListNode has no
    # __lt__ — so without a unique integer here this raises TypeError.
    heap: list[tuple[int, int, ListNode]] = []

    for index, head in enumerate(lists):
        if head:  # skip empty lists
            heapq.heappush(heap, (head.val, index, head))

    dummy = ListNode()
    tail = dummy

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

        tail.next = node
        tail = node

        if node.next:
            heapq.heappush(heap, (node.next.val, index, node.next))

    return dummy.next

Two traps, one per language

Python — pushing (node.val, node) crashes on ties. When two values are equal, Python falls through to comparing the next element, and ListNode has no < operator. The error is a TypeError that only appears on inputs containing duplicates, so it passes small tests and fails big ones. The fix is the list index as a middle element: it is unique, so comparison never reaches the node.

TypeScript — the final tail.next = null is not decoration. The last node you append still carries its original next pointer. Without cutting it, you may return a list with extra nodes on the end, or a cycle.

Complexity Analysis

Time Complexity

O(N log k)

Space Complexity

O(k)

Where N is the total number of nodes across all lists and k is the number of lists.

Time — every node enters and leaves the heap exactly once. Each of those 2N operations costs O(log k), because the heap never holds more than one node per list.
Space — the heap holds at most k nodes. The output reuses the existing nodes rather than allocating new ones, so no extra space is needed for the result.

Compared with the alternatives

Approach	Time	Space	Note
Scan all `k` heads each step	`O(N · k)`	`O(1)`	Fine for `k ≤ 3`
Merge lists one at a time	`O(N · k)`	`O(1)`	Deceptive — the first list is re-walked `k` times
Heap of heads	`O(N log k)`	`O(k)`	The standard answer
Divide and conquer, merge in pairs	`O(N log k)`	`O(log k)`	Same time, no heap needed

Why merging one at a time is slower than it looks

Merging list 1 into an accumulator, then list 2, then list 3… feels linear. It is not.

The accumulator grows as you go, and every merge walks it from the start again. The first list gets traversed k times, giving O(N · k).

Pairing them instead — merge 1+2, 3+4, then merge the results — means each node is touched only log k times. Same result as the heap, and it needs no extra structure.

Edge Cases

Merge Two Sorted Lists — the k = 2 case, and the source of the dummy-head trick
Kth Largest Element in an Array — the other core heap move, keeping only k candidates
Merge Sorted Array — the same merge, in place and backwards
Heaps — why push and pop cost O(log k)

Merge k Sorted Lists

lists is empty, i.e. []

lists contains empty lists, e.g. [[], [1], []]

Every list is empty, e.g. [[], []]

Only one list, e.g. [[1, 2, 3]]

Duplicate values across lists

On this page