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 Plain-English Breakdown

You are given an array lists. Each item in this array is a completely separate linked list, and each of those lists is already sorted in ascending order. Your job is to take all these separate sorted chains and weave them together into one giant, single, sorted linked list.

Constraints to note:

• k (number of lists) is up to 10^4.
• Total nodes N is up to 10^4.
• O(N^2) approaches or slow merges will Time Out.

(The brute force approach is discussed in the Pattern section below).

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.

ELI5 Analogy: Imagine you have k separate lines of people waiting to buy tickets, and everyone in each line is sorted by height (shortest at the front). You want to merge them into one single line sorted by height. You only need to look at the people currently at the very front of the k lines. You pull the absolute shortest person out of those k front-runners and put them in your new mega-line. Then, the next person in that specific line steps up to the front. You repeat this until all lines are empty! A Min-Heap is just a magical tool that instantly hands you the shortest person out of a group without you having to scan all k lines manually every time.

Code Walkthrough (Heap Approach)

1. The Heap Setup: We initialize an empty list heap. We iterate over the k linked lists. For every list head that isn't null, we push it into the heap. We store a tuple: (node.val, i, node). i is the index of the list in the array, used purely as a tie-breaker so Python never tries to compare two ListNode objects.
2. The Dummy Node: We create a dummy node to build our mega-list upon, and a tail pointer to keep track of the end of it.
3. The Pop and Push Loop: while heap: means while we still have nodes to process. We heappop() the smallest element. We grab the node from it.
4. Linking: We attach node to our tail.next, and then advance tail = node.
5. Advancing the specific line: If the node we just attached has a .next node (meaning that specific ticket line isn't empty yet), we heappush() that next node back into the heap. We reuse the same list index i.
6. Result: Once the heap is empty, all lines are processed. We return dummy.next.

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.

Derivation:

• Time Complexity: There are N nodes in total across all lists. Every single node gets pushed into the heap exactly once, and popped from the heap exactly once. The size of the heap is at most k (one node per list). A push/pop operation on a heap of size k takes O(\log k) time. Doing this for N nodes yields O(N \log k) time.
• Space Complexity: O(k) auxiliary space. The heap stores at most k nodes at any given time (one from each of the k lists). The output list reuses existing nodes, so it doesn't add to auxiliary 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.