4.9.10 — Merge K Sorted Lists

LeetCode 23 · Hard · ★ Blind 75

The problem

Merge k sorted linked lists into one sorted list.

[[1,4,5], [1,3,4], [2,6]]   →   1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Up to 10,000 lists, with up to 10,000 nodes in total.

The pattern

You already know how to merge two (4.9.2). The question is how to extend that to k, and there are three answers with genuinely different costs.

Let N be the total number of nodes.

The naive extension — merge them one at a time. Merge list 1 with list 2, then that result with list 3, and so on.

This is O(N k), and the reason is worth seeing. The accumulated list grows each time, and every merge walks all of it again. After merging in the last list, you have walked the accumulated result k times. That is the waste.

Two ways to fix it.

Solution 1 — a heap of the k current heads

At any moment, the next node of the answer is the smallest among the k list heads. A min-heap of size k gives you that smallest in O(\log k).

Take the smallest, attach it, and push that list's next node in its place.

Python

import heapq

class Solution:
    def mergeKLists(self, lists):
        heap = []
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))    # i breaks ties

        dummy = ListNode()
        tail = dummy

        while heap:
            val, 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

TypeScript

// TypeScript has no built-in heap; assume a MinHeap keyed by node value.
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const heap = new MinHeap<ListNode>((a, b) => a.val - b.val);
  for (const node of lists) if (node) heap.push(node);

  const dummy = new ListNode();
  let tail = dummy;

  while (heap.size > 0) {
    const node = heap.pop()!;
    tail.next = node;
    tail = node;
    if (node.next) heap.push(node.next);
  }

  return dummy.next;
}

The i in the tuple is not decoration. Python compares tuples element by element. When two nodes have equal values, it moves on to compare the next element — and ListNode objects have no < defined, so it raises TypeError. Inserting the list index as a tiebreaker means the comparison never reaches the node. This is the bug everybody hits once.

The heap holds at most k items, one per list, so every push and pop is O(\log k).

O(N \log k) time, O(k) space.

Solution 2 — merge in pairs

Merge list 1 with 2, 3 with 4, 5 with 6, and so on. That halves the number of lists. Repeat until one remains.

Python

class Solution:
    def mergeKLists(self, lists):
        if not lists:
            return None

        while len(lists) > 1:
            merged = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None
                merged.append(self.mergeTwo(l1, l2))
            lists = merged

        return lists[0]

    def mergeTwo(self, l1, l2):
        dummy = ListNode()
        tail = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next, l1 = l1, l1.next
            else:
                tail.next, l2 = l2, l2.next
            tail = tail.next
        tail.next = l1 or l2
        return dummy.next

Why this is also O(N \log k). Each round halves the number of lists, so there are \log k rounds. In each round, every node is touched exactly once, which is O(N). Multiply: O(N \log k).

Compare that with the naive one-at-a-time version. There, the accumulated list is walked k times. Here it is walked \log k times. For k = 10,000 that is 10,000 versus about 14.

O(1) extra space beyond the list of heads, and no heap needed. This is the version to write if the language has no heap in its standard library, which is the case in JavaScript.

Which to write

They have the same complexity. The heap version is better when the lists arrive as a stream, or when k is huge and you cannot hold all the heads. Pairwise merging is better when you have everything up front and want to avoid the heap's constant factor and its tiebreaker awkwardness.

Say both, pick one, and say why.

Complexity summary

approach	time	space
one at a time	O(N k)	O(1)
heap of heads	O(N \log k)	O(k)
pairwise merging	O(N \log k)	O(1)

Where this goes next

The k-way merge is a genuinely important operation, not just an exercise:

• External sorting — a file too large for memory is split into sorted chunks, then merged k ways with a heap. That is how databases sort, and how sort handles a file bigger than RAM.
• LSM tree compaction — merging sorted runs is exactly what a log-structured storage engine does in the background. Chapter 7.3.3.
• Merging sorted result sets from several database shards. Chapter 10.6.
• Kth Smallest Element in a Sorted Matrix, Smallest Range Covering K Lists — the same heap-of-heads structure.

The rule: when you need the smallest across k ordered sources, keep one candidate from each in a heap.

What the interviewer will push on

"Why is merging one at a time O(Nk)?" The accumulated list is rewalked on every merge.

"Why does pairwise merging fix it?" Halving gives \log k rounds, and each round touches every node once.

"Why do you push a tuple with an index into the heap?" Ties compare the next element, and nodes are not comparable.

"What is the heap's size?" k, never more, because you push one replacement per pop.

"Where does this appear in real systems?" External sort, LSM compaction, sharded queries. Naming one is a strong finish.

One thing to volunteer: give the complexity of all three approaches in one breath, then pick. That comparison is the answer to this problem — the merging itself you already knew.

Next: 4.9.11 Reverse Nodes in K-Group — the hardest pointer bookkeeping in the chapter.