Blind 75Hard

Merge k Sorted Lists — Min-Heap Merge

Push the head of each list into a min-heap and repeatedly extract the smallest node to build the merged list.

HeapLinked ListDivide and Conquer

View problem on LeetCode

Problem Statement

Merge k sorted linked lists into one sorted list.

Why This Problem Matters

Introduces the min-heap pattern for k-way merges used in external sorting and streaming.
Highlights trade-offs between heap-based and divide-and-conquer solutions.
Scaling up from two-list merge demonstrates algorithm generalisation.

Thought Process

Consider pairwise merging

Repeatedly merging lists works but can degrade to O(kN).

Prefer a min-heap

Keeping the smallest head available lets you append nodes in O(log k) per extraction.

Handle null lists gracefully

Only non-null heads should be inserted into the heap.

Step-by-Step Reasoning

Initialise a min-heap ordered by node value.
Insert the head of every non-empty list into the heap.
Pop the smallest node, append it to the merged list, and push its next node if present.
Repeat until the heap is empty.

Dry Run

Heap initially contains {1(l1),1(l2),2(l3)}

Extract 1 from l1, push 4; merged list starts 1.

Heap contains {1(l2),2(l3),4(l1)}

Extract 1 from l2, push 3; merged grows to 1→1.

Complexity Analysis

Time

O(N log k)

Space

O(k)

Why

Each of N nodes enters and leaves the heap once; the heap holds up to k nodes.

Annotated Solution

JAVA

import java.util.Comparator;
import java.util.PriorityQueue;

public class MergeKSortedLists {
  public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
    for (ListNode node : lists) {
      if (node != null) {
        heap.offer(node);
      }
    }

    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    while (!heap.isEmpty()) {
      ListNode node = heap.poll();
      tail.next = node;
      tail = tail.next;
      if (node.next != null) {
        heap.offer(node.next);
      }
    }

    return dummy.next;
  }

  public static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
  }
}

A min-heap always exposes the smallest current node. Each extraction appends one node to the merged list and inserts its successor if it exists.

Common Pitfalls

Inserting null nodes into the heap leads to NullPointerException when dereferencing.
Forgetting to push node.next loses parts of lists.
Using integers instead of nodes breaks stability and wastes memory.

Follow-Up Questions

How does divide-and-conquer merging compare in practice?
Can you merge streams of numbers lazily without materialising lists?

Key Takeaways

Min-heaps generalise pairwise merges to k lists cleanly.

Think about memory usage—storing only k heads keeps the footprint small.

Comparing heap vs divide-and-conquer approaches is a good interview discussion.