6.2 K-way Merge

Demo: Merge k Sorted Lists — LC 23 (Hard — Amazon/Meta/Google High)

Statement (Demo): Given an array of k sorted linked lists, merge them into one sorted linked list and return its head. Example: lists=[[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6] | ⚡ k ≤ 10⁴, total nodes ≤ 10⁴

Approach: Put the head of every non-empty list into a min-heap ordered by value. Pop the smallest node, attach it to the result (dummy node, see 3.2), and push that node's next. The heap never holds more than k nodes. (MinHeap → 6.1.)

function mergeKLists(lists) {
  const heap = new MinHeap((a, b) => a.val - b.val);
  for (const head of lists) if (head) heap.push(head);
  const dummy = { next: null };
  let tail = dummy;
  while (heap.size) {
    const node = heap.pop(); // smallest current head
    tail.next = node;
    tail = node;
    if (node.next) heap.push(node.next); // its successor joins the race
  }
  return dummy.next;
}

Complexity: Time O(N log k) for N total nodes, Space O(k) (divide-and-conquer pairwise merging is the heap-free alternative)