Merge K Sorted Lists (LC 23)

Pattern: Min-Heap of Heads (K-way Merge) — alternative: Divide & Conquer pairs Difficulty: Hard Key Concept: Push the head node of each list into a min-heap. Repeatedly poll the smallest, append it to the result, and push its next.

Problem Statement

You are given an array of k linked lists, each sorted in ascending order. Merge all 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

---

1. Algorithm & Pseudocode

Min-Heap

heap = min-heap by node.val
for each list head h in lists:
    if h != null: heap.offer(h)

dummy = new ListNode(); tail = dummy
while heap not empty:
    node = heap.poll()
    tail.next = node; tail = node
    if node.next != null: heap.offer(node.next)
return dummy.next

Divide & Conquer

Merge pairs of lists (LC 21), halve the array of lists, repeat until one remains.

---

2. Step-by-Step Analysis

Why a heap of heads At any moment the next node to output is the smallest value among the current heads of the not-yet-exhausted lists. A min-heap delivers that in O(log k).

Why we don’t bulk-load all nodes Putting every node into the heap would be O(N log N) instead of O(N log K) — when K << N this is significantly slower (and uses N space inside the heap).

Why divide & conquer also works Merging pairs is O(n+m); halving the list count k times gives total work O(N log K) — same as heap.

ASCII Trace for [1→4→5, 1→3→4, 2→6]

initial heap: [1(L1), 1(L2), 2(L3)]

poll 1(L1) → result 1; push 4(L1)   heap=[1(L2),4(L1),2(L3)]→[1(L2),2(L3),4(L1)]
poll 1(L2) → result 1; push 3(L2)   heap=[2(L3),3(L2),4(L1)]
poll 2(L3) → result 2; push 6(L3)   heap=[3(L2),4(L1),6(L3)]
poll 3(L2) → result 3; push 4(L2)   heap=[4(L1),4(L2),6(L3)]
poll 4(L1) → result 4; push 5(L1)   heap=[4(L2),5(L1),6(L3)]
poll 4(L2) → result 4; (L2 done)    heap=[5(L1),6(L3)]
poll 5(L1) → result 5; (L1 done)    heap=[6(L3)]
poll 6(L3) → result 6                heap=[]

result: 1→1→2→3→4→4→5→6

---

3. Java Solution

Min-Heap

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode h : lists) if (h != null) heap.offer(h);

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

Time: (O(N \log K)) where N = total nodes, K = number of lists Space: (O(K))

Divide & Conquer

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }
    private ListNode merge(ListNode[] lists, int lo, int hi) {
        if (lo == hi) return lists[lo];
        int mid = (lo + hi) >>> 1;
        return mergeTwo(merge(lists, lo, mid), merge(lists, mid + 1, hi));
    }
    private ListNode mergeTwo(ListNode a, ListNode b) {
        ListNode dummy = new 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;
    }
}

Time: (O(N \log K)) Space: (O(\log K)) recursion stack

---

4. The “Java vs. Others” Edge

• Subtraction comparator (a,b) -> a.val - b.val is safe here because LC values fit in int. For risky ranges use Integer.compare(a.val, b.val).
• The heap stores node references, not values, so re-inserting node.next is O(1) plus the standard heap O(log K).
• Reusing input nodes (no allocation) keeps space at O(K) — required for “in-place” expectation.

---

5. Complexity Summary

Approach	Time	Space	Notes
Min-Heap	(O(N \log K))	(O(K))	Cleanest, idiomatic in Java
Divide & Conquer	(O(N \log K))	(O(\log K))	Same time, slightly less memory
Naive merge-each	(O(N \cdot K))	(O(1))	Reject — much slower