23. Merge k Sorted Lists

At every step we want the smallest of the k current heads. A min-heap holding exactly those k heads gives us that in O(log k) per pop, so all N nodes go through at O(log k) cost each.

Setup

A min-heap stores tuples so Python compares them lexicographically: first the value, then a tiebreaker, then the node itself. We need the tiebreaker because when two values are equal Python would otherwise try to compare ListNode objects directly, which raises a TypeError (no < defined on ListNode).

Steps

1. Initialise dummy = tail = ListNode(0) and heap = [].
2. Seed: for each non-empty list head node at position i, push (node.val, i, node) onto the heap.
3. While the heap is non-empty:
   • Pop the smallest tuple — this is the next node in sorted order.
   • Splice it onto the tail: tail.next = node, then tail = tail.next.
   • If node.next exists, push (node.next.val, i, node.next) onto the heap. (We reuse the same i so future ties from the same list still have a valid tiebreaker.)
4. Return dummy.next.

Walk-through

Three lists: A = [1, 4, 5] (i=0), B = [1, 3, 4] (i=1), C = [2, 6] (i=2).

Initial heap (top is smallest): [(1, 0, A1), (1, 1, B1), (2, 2, C1)].

Result: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6. ✓

Why we cap heap size at k

We only push the next node from a list after popping a node from that list. So at any moment the heap holds at most one node per list — at most k entries total. That's where the O(log k) per operation comes from.

Edge cases

• Some lists empty (None): the seeding step skips them. The heap may start with fewer than k entries; that's fine.
• All lists empty: the heap stays empty, the loop never runs, return dummy.next = None.
• Equal values across lists: the i tiebreaker keeps heapq from comparing ListNode objects.

Complexity

• Time: O(N log k) — each of N nodes is pushed once and popped once, each operation is O(log k).
• Space: O(k) — the heap.

import java.util.*;

class Solution {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int v) { val = v; }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        ListNode[] nodes = new ListNode[lists.length];
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                nodes[i] = lists[i];
                heap.offer(new int[]{lists[i].val, i});
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int idx = top[1];
            tail.next = nodes[idx];
            tail = tail.next;
            if (nodes[idx].next != null) {
                nodes[idx] = nodes[idx].next;
                heap.offer(new int[]{nodes[idx].val, idx});
            }
        }
        return dummy.next;
    }
}

Pair up the k lists and merge each pair using the two-list merge from the previous problem. After one round you have k/2 lists; after another, k/4; and so on. After log k rounds, only one list remains.

Why pair-merging beats one-by-one merging

A naive approach repeatedly merges list i+1 into a running result. After i merges the running list has roughly i · (N/k) nodes, and the next merge touches all of them — leading to O(N · k) total work.

Pair-merging avoids that: at level ℓ, each merge handles roughly N / (k / 2^ℓ) nodes, but there are k / 2^ℓ merges, so each level does O(N) work. With log k levels, total is O(N log k).

Steps

1. Edge case: if lists is empty, return None.
2. While len(lists) > 1:
   • Walk lists two at a time. For each pair (a, b) (with b = None if lists has odd length and we're at the last item), call mergeTwoLists(a, b) and append the result to a new array merged.
   • Replace lists with merged.
3. Return lists[0].

Walk-through

Start with 4 lists: A = [1, 4, 5], B = [1, 3, 4], C = [2, 6], D = [0, 7].

Round 1: pair (A, B) → [1, 1, 3, 4, 4, 5]
         pair (C, D) → [0, 2, 6, 7]
         lists = [AB, CD]

Round 2: pair (AB, CD) → [0, 1, 1, 2, 3, 4, 4, 5, 6, 7]
         lists = [merged]

Done. Return merged.

For 5 lists [A, B, C, D, E]:

Round 1: pair (A, B), pair (C, D), pair (E, None) → 3 lists
Round 2: pair (AB, CD), pair (E, None)            → 2 lists
Round 3: pair (ABCD, E)                           → 1 list

The odd-list-out at any round just "merges with None", which mergeTwoLists handles naturally — it returns the non-None side immediately.

Why O(N log k)

Let N be the total number of nodes across all lists. At each round, every node passes through exactly one merge — so each round costs O(N). The number of rounds is ⌈log₂ k⌉. Total: O(N log k).

Edge cases

• Empty input: return None.
• One list only: the while doesn't execute; return lists[0].
• Some lists empty (None): mergeTwoLists handles that — pairing with None just returns the other side.

Complexity

• Time: O(N log k).
• Space: O(log k) for the pairing recursion (or O(k) for the rebuilt lists array each round, depending on how you count).