Typorithm · hard

Merge K Sorted Lists

merge-k-sorted-listsheapsmin-heapk-way-mergecomparator

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Merge K Sorted Lists

Heaps

A min-heap of the k current heads yields the smallest node each step; splice it onto a dummy-led result and refill from its list.

Merging k sorted lists by comparing all heads each step would be O(nk); a heap makes each pick O(log k).

Seed a min-heap (with a value comparator) with every non-null head, holding at most k nodes.

Repeatedly pop the smallest, append it to a dummy-led chain, and push its next, for O(n log k) total.

Heap holds the k current heads.

Pop min, splice, push its next.

Dummy node simplifies the head.

function mergeKLists(lists) {
  const heap = new MinHeap((a, b) => a.val - b.val);
  for (const node of lists) {
    if (node !== null) {
      heap.push(node);
    }
  }

  const dummy = { val: 0, next: null };
  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;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Heap by node value

JS has no built-in priority queue, so pass a comparator to order nodes.

const heap = new MinHeap((a, b) => a.val - b.val)

2. Seed the heads

Start with each list's head so the heap holds at most k nodes.

heap.push(node)

3. Smallest head

The heap's minimum is the next node of the merged list.

const node = heap.pop()

4. Refill from its list

Push the popped node's successor to keep all lists represented.

if (node.next !== null) {
      heap.push(node.next)

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.