Merge K Sorted Lists | Heap & Divide Conquer | Linked List

Overview

Merge k sorted lists means combining k sorted linked lists into one sorted list. Two main approaches: (1) Min-heap (priority queue): repeatedly take the smallest head among the k lists, append it to the result, and push the next node from that list into the heap. O(N log k) time where N is total nodes and k is the number of lists. (2) Divide and conquer (merge pairs): merge list 0 with 1, 2 with 3, etc., then merge the results in pairs until one list remains. O(N log k) as well. Both use the same Merge Two Sorted as a building block.

Key idea: The current minimum over all k heads is always at one of the heads; a min-heap lets you get that minimum and advance in O(log k). Alternatively, pairwise merging reduces k to 1 in O(log k) rounds, each round doing O(N) work.

When to Use

Merge k sorted lists — Exact problem.
External merge sort — K-way merge of sorted runs.

How It Works

Min-heap approach:

Put the head of each non-empty list into a min-heap (compare by node value; you need to store the node or (value, list index) and be able to get the next node from that list).
While the heap is not empty: pop the smallest node, append it to the result (dummy + tail), and if that node has a next, push next into the heap.
Return dummy.next.

Divide and conquer:

While there is more than one list: merge lists in pairs (list[i] with list[i+1]), store results, then replace the array with the merged results; repeat until one list remains.
Return that list.

Example 1: Merge K Lists with Min-Heap

Problem: You are given an array of k linked lists, each sorted in ascending order. Merge all into one sorted list.

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  const heap: ListNode[] = [];
  const cmp = (a: ListNode, b: ListNode) => a.val - b.val;
  for (const head of lists) {
    if (head !== null) heap.push(head);
  }
  if (heap.length === 0) return null;
  heap.sort(cmp);
  const dummy = new ListNode(-1);
  let tail = dummy;
  while (heap.length > 0) {
    const node = heap.shift()!;
    tail.next = node;
    tail = tail.next;
    if (node.next !== null) {
      heap.push(node.next);
      heap.sort(cmp);
    }
  }
  tail.next = null;
  return dummy.next;
}

Using array + sort each time gives O(N k) per extraction; a real min-heap gives O(log k). For a proper O(N log k) implementation use a priority queue that supports insert and extractMin in O(log size).

Example 2: Merge K Lists with Divide and Conquer

Problem: Same; use pairwise merge.

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  if (lists.length === 0) return null;
  let arr = lists.filter((l) => l !== null);
  while (arr.length > 1) {
    const next: (ListNode | null)[] = [];
    for (let i = 0; i < arr.length; i += 2) {
      const a = arr[i];
      const b = i + 1 < arr.length ? arr[i + 1] : null;
      next.push(mergeTwo(a!, b));
    }
    arr = next;
  }
  return arr[0] ?? null;
}
function mergeTwo(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode(-1);
  let tail = dummy;
  while (l1 && 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 ?? l2;
  return dummy.next;
}

Time: O(N log k). Space: O(1) for merge (stack O(log k) for recursion if implemented recursively).

Edge Cases

Empty array — Return null.
All lists null/empty — Return null.
Single list — Return that list.
One list long, others short — Heap stays small; pairwise merge also handles.

Common Mistakes

Heap comparison — Compare by node value; when storing nodes, ensure you don't mutate the same node from two places.
Pushing next — After appending a node to the result, push node.next (if not null) into the heap so that list continues to contribute.
Tail.next = null — In heap approach, the last node appended might have a stale .next from its original list; set tail.next = null at the end to avoid cycles.

Time and Space Complexity

Time: O(N log k) for both heap and divide-and-conquer.
Space: O(k) for heap; O(1) extra for pairwise merge (excluding recursion).

Summary

Merge k sorted lists: Min-heap of k heads, repeatedly pop min and push its next; or pairwise merge using Merge Two Sorted until one list remains.
See Merge Two Sorted and Dummy Head for the two-list merge.