#23 · Linked List

Merge k Sorted Lists

Given an array of k sorted linked lists, merge them into one sorted linked list and return its head.

HardLeetCode

Current node
Link just rewired
Done / in result
Marked
Rejected
Dummy head

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Min-heap (priority queue)

A binary heap keeps the smallest element at the top. Push and pop each cost O(log m) for a heap of m elements. Holding one node per list means m = k, so choosing the next output node among k candidates costs O(log k) instead of O(k).

Memory layout

A contiguous array where the children of index i live at 2i+1 and 2i+2: no pointers, cache friendly. Heap size never exceeds k.

Operation	Cost
push / pop	O(log k)
peek smallest	O(1)
merge all N nodes	O(N log k) time, O(k) space

Two-way merge as a building block

Merging two sorted lists is a linear, in-place, O(1)-space operation: compare heads, splice the smaller. If lists are merged in pairs, each node is touched once per round, and there are only ⌈log₂ k⌉ rounds.

Memory layout

Nodes are re-linked in place with a dummy head: no allocation.

Operation	Cost
merge two lists of total length m	O(m)
pairwise (divide and conquer)	O(N log k) time, O(1) extra space

Why it fits

Each input list is already sorted, so the global minimum is always at one of the k list heads: a structure that finds the minimum of k items quickly (a heap) turns the k-way merge into N cheap steps.
Merging lists in balanced pairs makes every node participate in only log k merges, versus up to k merges when folding one list at a time.
Both approaches re-link existing nodes instead of copying, so memory stays O(k) or O(1) beyond the input.

Why alternatives degrade

Dump everything into an array and sort:: O(N log N) and O(N) space; it throws away the sortedness of the inputs, so log N replaces log k.
Scan all k heads for the minimum every time:: O(k) per output node: O(N·k) total, which is slow when k is large.
Fold: merge list 1 with 2, then the result with 3, …:: The accumulated list is re-walked on every merge: O(k·N) in the worst case (lopsided sizes make it quadratic).

Four approaches, from naive to production

1 · beginner

Collect, sort, rebuild

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

Copy all values from all lists into one array, sort it, and build a new linked list from it.

ListNode* mergeKLists(vector<ListNode*>& lists) {
    vector<int> vals;
    for (ListNode* head : lists) {
        for (ListNode* n = head; n; n = n->next) vals.push_back(n->val);
    }
    sort(vals.begin(), vals.end());
    ListNode* dummy = new ListNode(0);
    ListNode* tail = dummy;
    for (int v : vals) {
        tail->next = new ListNode(v);
        tail = tail->next;
    }
    return dummy->next;
}

public ListNode mergeKLists(ListNode[] lists) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode head : lists) {
        for (ListNode n = head; n != null; n = n.next) vals.add(n.val);
    }
    Collections.sort(vals);
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    for (int v : vals) {
        tail.next = new ListNode(v);
        tail = tail.next;
    }
    return dummy.next;
}

def merge_k_lists(lists):
    vals = []
    for head in lists:
        n = head
        while n:
            vals.append(n.val)
            n = n.next
    vals.sort()
    dummy = ListNode(0)
    tail = dummy
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  const vals: number[] = [];
  for (const head of lists) {
    for (let n = head; n; n = n.next) vals.push(n.val);
  }
  vals.sort((a, b) => a - b);
  const dummy = new ListNode(0);
  let tail = dummy;
  for (const v of vals) {
    tail.next = new ListNode(v);
    tail = tail.next;
  }
  return dummy.next;
}

Flaws & bottlenecks

Ignores that every input list is already sorted, paying log N instead of log k.
Allocates N new nodes plus an N-element array, and the original nodes are discarded.
Needs all the data in memory at once: no streaming.

Interviewer cross-questions

How do you use the fact that the lists are sorted?

Say: The smallest remaining value is always at the head of one of the lists, so you only ever need to compare k values. A heap does that in O(log k), or merge the lists pairwise with the linear two-list merge.

What is the space cost?

Say: O(N): the array of values plus N new nodes. The heap and pairwise approaches re-link the existing nodes and need only O(k) or O(1) extra.

When is this acceptable?

Say: For small inputs or one-off scripts. It is simple and obviously correct, but it does not scale to large k or N.

2 · intermediate

Merge one list at a time

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

Keep an accumulated result and merge each list into it with the standard two-list merge, one after another.

ListNode* mergeTwo(ListNode* a, ListNode* b) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }
        else { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode* acc = nullptr;
    for (ListNode* list : lists) {
        acc = mergeTwo(acc, list);
    }
    return acc;
}

public ListNode mergeKLists(ListNode[] lists) {
    ListNode acc = null;
    for (ListNode list : lists) {
        acc = mergeTwo(acc, list);
    }
    return acc;
}

private ListNode mergeTwo(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0);
    ListNode 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 != null ? a : b;
    return dummy.next;
}

def merge_k_lists(lists):
    acc = None
    for lst in lists:
        acc = merge_two(acc, lst)
    return acc

def merge_two(a, b):
    dummy = ListNode(0)
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  let acc: ListNode | null = null;
  for (const list of lists) {
    acc = mergeTwo(acc, list);
  }
  return acc;
}

function mergeTwo(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a && b) {
    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;
}

Flaws & bottlenecks

The accumulated list is re-walked on every merge, so early nodes are processed up to k times.
Quadratic if one list is huge and many are tiny (or in lists-of-equal-size: O(k²·n)).
The structure is correct but the growth of acc makes later merges ever more expensive.

Interviewer cross-questions

What is the complexity with k lists of length n each?

Say: The i-th merge handles about i·n nodes, so the total is n·(1 + 2 + … + k) = O(k²·n) = O(k·N), where N = k·n is the total number of nodes.

How do you reduce the re-walking?

Say: Merge in balanced pairs (like merge sort) so the lists being merged have similar size, or keep only the k heads in a heap.

Does it matter in which order you fold?

Say: Yes: merging the shortest lists first (Huffman style) minimizes total work, but a balanced pairwise merge already achieves O(N log k).

3 · advanced

Min-heap of list heads

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

Keep one node from each list in a min-heap. Repeatedly pop the smallest, append it to the result, and push its successor.

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* x, ListNode* y) { return x->val > y->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);
    for (ListNode* head : lists) if (head) heap.push(head);
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (!heap.empty()) {
        ListNode* node = heap.top(); heap.pop();
        tail->next = node;
        tail = node;
        if (node->next) heap.push(node->next);
    }
    return dummy.next;
}

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>((x, y) -> Integer.compare(x.val, y.val));
    for (ListNode head : lists) if (head != null) heap.add(head);
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (!heap.isEmpty()) {
        ListNode node = heap.poll();
        tail.next = node;
        tail = node;
        if (node.next != null) heap.add(node.next);
    }
    return dummy.next;
}

def merge_k_lists(lists):
    heap = []
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(heap, (head.val, i, head))
    dummy = ListNode(0)
    tail = dummy
    while heap:
        _, 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

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  const heap = new MinHeap<ListNode>((x, y) => x.val < y.val);
  for (const head of lists) if (head) 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) heap.push(node.next);
  }
  return dummy.next;
}

class MinHeap<T> {
  private a: T[] = [];
  constructor(private less: (x: T, y: T) => boolean) {}
  get size() { return this.a.length; }
  push(v: T) {
    const a = this.a;
    a.push(v);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop(): T {
    const a = this.a;
    const top = a[0];
    const last = a.pop()!;
    if (a.length) {
      a[0] = last;
      let i = 0;
      for (;;) {
        let m = i;
        const l = 2 * i + 1, r = l + 1;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

Flaws & bottlenecks

Needs a heap implementation (not in every standard library: JavaScript has none); the constant factors of heap operations are higher than a plain linked-list merge.
The heap array is O(k) extra memory.
In some languages ties require a tiebreaker (Python compares the node when values are equal and fails unless an index is added).

Interviewer cross-questions

Why is the heap size at most k?

Say: We keep exactly one candidate (the current head) per non-empty list. Popping a node and pushing its successor keeps that invariant, so the heap never exceeds k elements and each operation is O(log k).

How is it better than scanning k heads each time?

Say: A scan costs O(k) per output node (O(N·k) total). The heap gets the minimum in O(log k): O(N log k) total, a huge win when k is large.

Is the merge stable?

Say: Not by default: equal values may pop in any order. Add the list index as a tiebreaker (compare value, then list number) to make it stable.

4 · expert

Bottom-up pairwise merging

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

Merge list i with list i+gap in place, doubling gap each round (1, 2, 4, …). After ⌈log₂ k⌉ rounds everything is in lists[0]. No heap, no recursion.

ListNode* mergeTwo(ListNode* a, ListNode* b) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }
        else { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty()) return nullptr;
    for (int gap = 1; gap < (int)lists.size(); gap *= 2) {
        for (int i = 0; i + gap < (int)lists.size(); i += 2 * gap) {
            lists[i] = mergeTwo(lists[i], lists[i + gap]);
        }
    }
    return lists[0];
}

public ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    for (int gap = 1; gap < lists.length; gap *= 2) {
        for (int i = 0; i + gap < lists.length; i += 2 * gap) {
            lists[i] = mergeTwo(lists[i], lists[i + gap]);
        }
    }
    return lists[0];
}

private ListNode mergeTwo(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0);
    ListNode 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 != null ? a : b;
    return dummy.next;
}

def merge_k_lists(lists):
    if not lists:
        return None
    gap = 1
    while gap < len(lists):
        for i in range(0, len(lists) - gap, 2 * gap):
            lists[i] = merge_two(lists[i], lists[i + gap])
        gap *= 2
    return lists[0]

def merge_two(a, b):
    dummy = ListNode(0)
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  if (lists.length === 0) return null;
  for (let gap = 1; gap < lists.length; gap *= 2) {
    for (let i = 0; i + gap < lists.length; i += 2 * gap) {
      lists[i] = mergeTwo(lists[i], lists[i + gap]);
    }
  }
  return lists[0];
}

function mergeTwo(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a && b) {
    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;
}

Flaws & bottlenecks

Mutates the caller's lists array (and the nodes) to avoid allocation: copy it first if the caller still needs it.
Needs the lists to be re-linked in place, so the input lists cannot be reused afterwards.
The loop bounds (i + gap < n, i += 2·gap) are easy to get wrong when k is not a power of two.

Interviewer cross-questions

Why O(N log k)?

Say: Each round merges every list once, so it touches each of the N nodes once, and there are ⌈log₂ k⌉ rounds because the number of lists halves each time.

What if k is not a power of two?

Say: The last list in a round may have no partner (i + gap ≥ k); it simply waits and is merged in a later round. The loop condition i + gap < k handles that.

Heap or pairwise merge in production?

Say: Pairwise merging is usually faster (sequential access, no heap bookkeeping, O(1) extra space) when all lists are in memory. The heap is the right tool when the inputs are streams, since it only needs one element per input at a time.

Synchronized code walkthrough

Showing: Collect, sort, rebuild — shares the player above; click any step to jump.

ListNode* mergeKLists(vector<ListNode*>& lists) {
    vector<int> vals;
    for (ListNode* head : lists) {
        for (ListNode* n = head; n; n = n->next) vals.push_back(n->val);
    }
    sort(vals.begin(), vals.end());
    ListNode* dummy = new ListNode(0);
    ListNode* tail = dummy;
    for (int v : vals) {
        tail->next = new ListNode(v);
        tail = tail->next;
    }
    return dummy->next;
}

public ListNode mergeKLists(ListNode[] lists) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode head : lists) {
        for (ListNode n = head; n != null; n = n.next) vals.add(n.val);
    }
    Collections.sort(vals);
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    for (int v : vals) {
        tail.next = new ListNode(v);
        tail = tail.next;
    }
    return dummy.next;
}

def merge_k_lists(lists):
    vals = []
    for head in lists:
        n = head
        while n:
            vals.append(n.val)
            n = n.next
    vals.sort()
    dummy = ListNode(0)
    tail = dummy
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  const vals: number[] = [];
  for (const head of lists) {
    for (let n = head; n; n = n.next) vals.push(n.val);
  }
  vals.sort((a, b) => a - b);
  const dummy = new ListNode(0);
  let tail = dummy;
  for (const v of vals) {
    tail.next = new ListNode(v);
    tail = tail.next;
  }
  return dummy.next;
}

ListNode* mergeTwo(ListNode* a, ListNode* b) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }
        else { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode* acc = nullptr;
    for (ListNode* list : lists) {
        acc = mergeTwo(acc, list);
    }
    return acc;
}

public ListNode mergeKLists(ListNode[] lists) {
    ListNode acc = null;
    for (ListNode list : lists) {
        acc = mergeTwo(acc, list);
    }
    return acc;
}

private ListNode mergeTwo(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0);
    ListNode 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 != null ? a : b;
    return dummy.next;
}

def merge_k_lists(lists):
    acc = None
    for lst in lists:
        acc = merge_two(acc, lst)
    return acc

def merge_two(a, b):
    dummy = ListNode(0)
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  let acc: ListNode | null = null;
  for (const list of lists) {
    acc = mergeTwo(acc, list);
  }
  return acc;
}

function mergeTwo(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a && b) {
    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;
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* x, ListNode* y) { return x->val > y->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);
    for (ListNode* head : lists) if (head) heap.push(head);
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (!heap.empty()) {
        ListNode* node = heap.top(); heap.pop();
        tail->next = node;
        tail = node;
        if (node->next) heap.push(node->next);
    }
    return dummy.next;
}

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>((x, y) -> Integer.compare(x.val, y.val));
    for (ListNode head : lists) if (head != null) heap.add(head);
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (!heap.isEmpty()) {
        ListNode node = heap.poll();
        tail.next = node;
        tail = node;
        if (node.next != null) heap.add(node.next);
    }
    return dummy.next;
}

def merge_k_lists(lists):
    heap = []
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(heap, (head.val, i, head))
    dummy = ListNode(0)
    tail = dummy
    while heap:
        _, 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

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  const heap = new MinHeap<ListNode>((x, y) => x.val < y.val);
  for (const head of lists) if (head) 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) heap.push(node.next);
  }
  return dummy.next;
}

class MinHeap<T> {
  private a: T[] = [];
  constructor(private less: (x: T, y: T) => boolean) {}
  get size() { return this.a.length; }
  push(v: T) {
    const a = this.a;
    a.push(v);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop(): T {
    const a = this.a;
    const top = a[0];
    const last = a.pop()!;
    if (a.length) {
      a[0] = last;
      let i = 0;
      for (;;) {
        let m = i;
        const l = 2 * i + 1, r = l + 1;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

ListNode* mergeTwo(ListNode* a, ListNode* b) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }
        else { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty()) return nullptr;
    for (int gap = 1; gap < (int)lists.size(); gap *= 2) {
        for (int i = 0; i + gap < (int)lists.size(); i += 2 * gap) {
            lists[i] = mergeTwo(lists[i], lists[i + gap]);
        }
    }
    return lists[0];
}

public ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    for (int gap = 1; gap < lists.length; gap *= 2) {
        for (int i = 0; i + gap < lists.length; i += 2 * gap) {
            lists[i] = mergeTwo(lists[i], lists[i + gap]);
        }
    }
    return lists[0];
}

private ListNode mergeTwo(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0);
    ListNode 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 != null ? a : b;
    return dummy.next;
}

def merge_k_lists(lists):
    if not lists:
        return None
    gap = 1
    while gap < len(lists):
        for i in range(0, len(lists) - gap, 2 * gap):
            lists[i] = merge_two(lists[i], lists[i + gap])
        gap *= 2
    return lists[0]

def merge_two(a, b):
    dummy = ListNode(0)
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  if (lists.length === 0) return null;
  for (let gap = 1; gap < lists.length; gap *= 2) {
    for (let i = 0; i + gap < lists.length; i += 2 * gap) {
      lists[i] = mergeTwo(lists[i], lists[i + gap]);
    }
  }
  return lists[0];
}

function mergeTwo(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a && b) {
    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;
}