23. Merge k Sorted Lists

Given k sorted linked lists, merge them into one sorted list. The key insight is that you can reduce k lists to one in O(log k) rounds by repeatedly merging pairs — the same divide-and-conquer that powers merge sort.

● HardDivide & ConquerHeapMergeTypeScript

PROBLEM What we're solving

You receive an array of k sorted linked lists. Return one sorted linked list containing all nodes. Example: [[1,4,5], [1,3,4], [2,6]] → [1,1,2,3,4,4,5,6]. You see this in database merge phases, external sort, and anywhere you must unify pre-sorted streams.

KEY IDEA Shrink k each round — not one node at a time

Insight → merging two sorted lists costs O(n). If you naively add one list at a time you do k merges totalling O(N·k). Instead, merge pairs in parallel: after one round you have ⌈k/2⌉ lists; after log₂k rounds you have 1. Total work: O(N log k) — the same asymptotic savings that make merge sort beat insertion sort.

RECIPE Pairwise merge rounds

0 · Base case. Empty array → null. Single list → return it directly; no merging needed.
1 · Round loop. While more than one list remains, collect results of merging pairs into a new array. An odd list out is carried unchanged.
2 · mergeTwoLists. Classic two-pointer merge with a dummy head: compare front nodes, advance the smaller pointer, attach to tail. O(m+n).
3 · Repeat. Replace the working array with the smaller merged array until length is 1. Return that element.

Classic confusion → people try to merge into the firstlist sequentially: list0 ← merge(list0, list1), then list0 ← merge(list0, list2), … This is O(N·k) because the growing result list is re-scanned every time. Pairwise merging avoids that by keeping each merge balanced.

COST Complexity & the heap alternative

Merge one-by-one (sequential)

O(N·k)

Each of k merges re-scans the growing result.

Divide & conquer / min-heap

O(N log k)

log k rounds; O(k) heap space.

Min-heap approach

Insert the head of every list into a min-heap keyed by node.val. Pop the minimum, attach it to the result, push that node's next (if any). Also O(N log k) — same asymptotic complexity but different constant factors. The heap approach is easier to extend to a streaming setting; the pairwise approach needs all lists up front and is usually simpler to implement correctly in an interview.

Pattern transfer → the same divide-and-conquer merging drives Sort List (LC 148), Count of Smaller Numbers After Self (merge-sort variant), and any external merge-sort pipeline. The min-heap approach transfers to Kth Smallest Element in a Sorted Matrix and Find K Pairs with Smallest Sums.

RUN IT Divide & conquer — merge pairs each round

lists (;-separated):

step 0 / 8

STARTStart with 3 sorted lists. We will repeatedly merge pairs (divide & conquer) until one list remains.

1// Definition for singly-linked list.
2class ListNode {
3  val: number;
4  next: ListNode | null;
5  constructor(val = 0, next: ListNode | null = null) {
6    this.val = val;
7    this.next = next;
8  }
9}
10 
11// --- Approach 1: Divide & Conquer (matches the visualizer) ---
12▶function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
13▶  if (lists.length === 0) return null;
14 
15  // Repeatedly halve the list of lists, merging pairs each round
16▶  let current = lists.slice();
17  while (current.length > 1) {
18    const next: Array<ListNode | null> = [];
19    for (let i = 0; i < current.length; i += 2) {
20      if (i + 1 < current.length) {
21        next.push(mergeTwoLists(current[i], current[i + 1]));
22      } else {
23        next.push(current[i]); // odd list — carry it over
24      }
25    }
26    current = next;
27  }
28  return current[0];
29}
30 
31function mergeTwoLists(
32  a: ListNode | null,
33  b: ListNode | null,
34): ListNode | null {
35  const dummy = new ListNode(0);
36  let tail = dummy;
37  while (a !== null && b !== null) {
38    if (a.val <= b.val) { tail.next = a; a = a.next; }
39    else                 { tail.next = b; b = b.next; }
40    tail = tail.next!;
41  }
42  tail.next = a ?? b;
43  return dummy.next;
44}
45 
46// --- Approach 2: Min-Heap (O(N log k)) ---
47// import { MinHeap } from 'some-heap-library'; // or implement manually
48//
49// function mergeKListsHeap(lists: Array<ListNode | null>): ListNode | null {
50//   const heap = new MinHeap<ListNode>((a, b) => a.val - b.val);
51//   for (const head of lists) if (head) heap.push(head);
52//   const dummy = new ListNode(0);
53//   let tail = dummy;
54//   while (!heap.isEmpty()) {
55//     const node = heap.pop()!;
56//     tail.next = node;
57//     tail = tail.next;
58//     if (node.next) heap.push(node.next);
59//   }
60//   return dummy.next;
61// }

[1→4→5]L0[1→3→4]L1[2→6]L2

State

round

lists remaining

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

current

[]

i (pair idx)

dummy

tail

pair being merged / pair indexmerged resultcarried (odd list) / next arrayround countertail pointer (mergeTwoLists)

slowfast

TYPESCRIPT The solution, annotated

mergeKLists.ts
// Definition for singly-linked list.
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

// --- Approach 1: Divide & Conquer (matches the visualizer) ---
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (lists.length === 0) return null;

  // Repeatedly halve the list of lists, merging pairs each round
  let current = lists.slice();
  while (current.length > 1) {
    const next: Array<ListNode | null> = [];
    for (let i = 0; i < current.length; i += 2) {
      if (i + 1 < current.length) {
        next.push(mergeTwoLists(current[i], current[i + 1]));
      } else {
        next.push(current[i]); // odd list — carry it over
      }
    }
    current = next;
  }
  return current[0];
}

function mergeTwoLists(
  a: ListNode | null,
  b: ListNode | null,
): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a !== null && b !== null) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else                 { tail.next = b; b = b.next; }
    tail = tail.next!;
  }
  tail.next = a ?? b;
  return dummy.next;
}

// --- Approach 2: Min-Heap (O(N log k)) ---
// import { MinHeap } from 'some-heap-library'; // or implement manually
//
// function mergeKListsHeap(lists: Array<ListNode | null>): ListNode | null {
//   const heap = new MinHeap<ListNode>((a, b) => a.val - b.val);
//   for (const head of lists) if (head) heap.push(head);
//   const dummy = new ListNode(0);
//   let tail = dummy;
//   while (!heap.isEmpty()) {
//     const node = heap.pop()!;
//     tail.next = node;
//     tail = tail.next;
//     if (node.next) heap.push(node.next);
//   }
//   return dummy.next;
// }

Reading it block by block

Lines 15–16 — guard clauses. Empty input returns null; a single list is already merged. These let the main loop assume ≥ 2 lists exist at the start of each iteration.

Lines 18–29 — divide-and-conquer round loop. current holds the working list of lists. Each iteration walks it in steps of 2, merging adjacent pairs into next. An odd-indexed tail element (i + 1 >= current.length) is carried forward without merging — it will find a partner in the next round.

Lines 32–43 — mergeTwoLists. Standard two-pointer sentinel-node merge. A dummy head eliminates the special-case for the first node. tail.next = a ?? b appends whichever list still has nodes. O(m + n) time, O(1) extra space.

Approach 2 sketch (lines 46–58) — min-heap. Seed the heap with all k heads, then greedily pop the minimum node and push its successor. Both approaches are O(N log k); the heap requires O(k) auxiliary space while pairwise is O(log k) stack frames or O(k) for the temporary arrays.

Complexity → O(N log k) time — N total nodes, log k rounds of merging. O(k) extra space for the temporary arrays each round (or O(log k) if done recursively). The mergeTwoLists inner loop looks like it might be O(N²) but each node is touched in exactly one merge per round, and there are log k rounds, giving O(N log k) total.

INTERVIEWFollow-ups they'll ask

"Can you do it with O(1) extra space?" Not trivially — the pairwise approach needs temporary arrays. A true in-place merge of linked lists is significantly more complex; in practice the O(k) space is accepted.
"What if lists arrive as a stream (online)?" Switch to the min-heap approach: maintain a heap of k current heads and emit the minimum as each new element arrives.
"Implement without recursion." The iterative pairwise loop is already non-recursive. If you wrote the recursive divide-and-conquer version, describe converting it to an iterative bottom-up pass (what the loop above does).
"Return the kth node of the merged list." Merge normally, then walk k−1 steps. Or use a heap and stop after k pops — O(k log k) without building the whole list.
"What if k is very large (millions of lists)?" The min-heap stays at O(k) memory but k itself becomes the bottleneck. Consider a tournament tree or chunked parallel merge.

OPTIMAL Divide & Conquer

mergeKLists.ts
// Definition for singly-linked list.
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

// --- Approach 1: Divide & Conquer (matches the visualizer) ---
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (lists.length === 0) return null;

  // Repeatedly halve the list of lists, merging pairs each round
  let current = lists.slice();
  while (current.length > 1) {
    const next: Array<ListNode | null> = [];
    for (let i = 0; i < current.length; i += 2) {
      if (i + 1 < current.length) {
        next.push(mergeTwoLists(current[i], current[i + 1]));
      } else {
        next.push(current[i]); // odd list — carry it over
      }
    }
    current = next;
  }
  return current[0];
}

function mergeTwoLists(
  a: ListNode | null,
  b: ListNode | null,
): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a !== null && b !== null) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else                 { tail.next = b; b = b.next; }
    tail = tail.next!;
  }
  tail.next = a ?? b;
  return dummy.next;
}

// --- Approach 2: Min-Heap (O(N log k)) ---
// import { MinHeap } from 'some-heap-library'; // or implement manually
//
// function mergeKListsHeap(lists: Array<ListNode | null>): ListNode | null {
//   const heap = new MinHeap<ListNode>((a, b) => a.val - b.val);
//   for (const head of lists) if (head) heap.push(head);
//   const dummy = new ListNode(0);
//   let tail = dummy;
//   while (!heap.isEmpty()) {
//     const node = heap.pop()!;
//     tail.next = node;
//     tail = tail.next;
//     if (node.next) heap.push(node.next);
//   }
//   return dummy.next;
// }

ALT 1 Min-heap of k heads

O(N log k) time · O(k) space

Matches divide & conquer asymptotically and is the natural fit when lists arrive as a stream — keep a heap of the current front of each list and always emit the global minimum.

approach-2.ts
// A small binary min-heap keyed by node.val.
class NodeHeap {
  private data: ListNode[] = [];

  get size(): number {
    return this.data.length;
  }

  push(node: ListNode): void {
    this.data.push(node);
    let i = this.data.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.data[parent].val <= this.data[i].val) break;
      [this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
      i = parent;
    }
  }

  pop(): ListNode {
    const top = this.data[0];
    const last = this.data.pop()!;
    if (this.data.length > 0) {
      this.data[0] = last;
      let i = 0;
      const n = this.data.length;
      while (true) {
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        let smallest = i;
        if (left < n && this.data[left].val < this.data[smallest].val) smallest = left;
        if (right < n && this.data[right].val < this.data[smallest].val) smallest = right;
        if (smallest === i) break;
        [this.data[smallest], this.data[i]] = [this.data[i], this.data[smallest]];
        i = smallest;
      }
    }
    return top;
  }
}

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const heap = new NodeHeap();
  for (const head of lists) {
    if (head !== null) heap.push(head);
  }

  const dummy = new ListNode(0);
  let tail = dummy;
  while (heap.size > 0) {
    const node = heap.pop();
    tail.next = node;
    tail = node;
    if (node.next !== null) heap.push(node.next);
  }
  return dummy.next;
}

Note → Same O(N log k) as the divide-and-conquer optimal, but with O(k) heap space instead of O(log k). Preferred for an online/streaming merge where you cannot see all lists up front.

ALT 2 Sequential merge into an accumulator

O(N·k) time · O(1) space

The simplest correct approach: fold the lists one at a time into a single running result with the same two-list merge. Easy to write, but the accumulator is re-walked every fold.

approach-3.ts
function mergeTwoLists(
  a: ListNode | null,
  b: ListNode | null,
): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a !== null && b !== null) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else                { tail.next = b; b = b.next; }
    tail = tail.next!;
  }
  tail.next = a ?? b;
  return dummy.next;
}

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  let result: ListNode | null = null;
  for (const head of lists) {
    result = mergeTwoLists(result, head);
  }
  return result;
}

Note → Correct and O(1) auxiliary space, but the accumulator grows by n each fold and is re-scanned every time, giving O(N·k). Fine for small k; switch to pairwise or heap once k grows.

ALT 3 Collect, sort, rebuild

O(N log N) time · O(N) space

Ignore the fact that the inputs are sorted: dump every value into an array, sort it, then build a fresh list. Trivially correct but throws away the pre-sorted structure.

approach-4.ts
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const values: number[] = [];
  for (const head of lists) {
    let node = head;
    while (node !== null) {
      values.push(node.val);
      node = node.next;
    }
  }

  values.sort((x, y) => x - y);

  const dummy = new ListNode(0);
  let tail = dummy;
  for (const v of values) {
    tail.next = new ListNode(v);
    tail = tail.next;
  }
  return dummy.next;
}

Note → O(N log N) > O(N log k) whenever k < N, and it allocates N new nodes (O(N) space) instead of relinking the originals. Worth mentioning only as the obvious baseline.

MNEMONIC The one-liner

"Pair them up, merge, halve the count — log k rounds and you're done."

TRIGGERS When you see _ → reach for _

merge k sorted lists / streams	pairwise divide & conquer or min-heap
O(N log k) over O(N·k)	pair-merge rounds (like merge sort)
streaming / online merge of k sources	min-heap of size k
dummy head node in linked list	sentinel for clean tail attachment

SKELETON The reusable shape

skeleton.ts
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (lists.length === 0) return null;
  let current = lists.slice();
  while (current.length > 1) {
    const next: Array<ListNode | null> = [];
    for (let i = 0; i < current.length; i += 2) {
      next.push(i + 1 < current.length
        ? mergeTwoLists(current[i], current[i + 1])
        : current[i]);
    }
    current = next;
  }
  return current[0];
}

FLASHCARDS Tap to flip

Why is sequential merging O(N·k)?

Each of the k merges re-scans the entire growing result list, which grows by n each time.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of the pairwise divide-and-conquer approach?

QUESTION 02

You merge k=4 lists sequentially (append list1 into list0, then list2, then list3). What is the complexity?

QUESTION 03

Trace: mergeKLists([[1,4,5],[1,3,4],[2,6]]). What is the output?

QUESTION 04

What is the purpose of the dummy (sentinel) head node in mergeTwoLists?

QUESTION 05

How many rounds of pairwise merging does k=8 lists require?

QUESTION 06

An odd list (no partner in the current round) is:

QUESTION 07

Which approach is naturally suited to a streaming / online setting where lists arrive one at a time?

QUESTION 08

#23 · Merge k Sorted ListsGiven k sorted linked lists, merge them into one sorted list. Repeatedly merging pairs in O(log k) rounds — the same divide-and-conquer behind merge sort — beats the naive O(k) per-element approach.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Shrink k each round — not one node at a time

RECIPE Pairwise merge rounds

COST Complexity & the heap alternative

Min-heap approach

RUN IT Divide & conquer — merge pairs each round

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Divide & Conquer

ALT 1 Min-heap of k heads

ALT 2 Sequential merge into an accumulator

ALT 3 Collect, sort, rebuild

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _