23. Merge k Sorted Lists

Merge k Sorted Lists is where the two-list merge you already know stops scaling, and the fix — a heap or pairwise merging — is the same trick that powers external sorting and k-way merges in real databases. It sits in the linked list pattern family, but the interesting part is the k in the complexity, not the pointer juggling.

The problem

You’re handed an array of k linked lists, each already sorted ascending, and you have to splice them into one sorted list and return its head. (Full statement on LeetCode.)

So [[1,4,5], [1,3,4], [2,6]] comes back as 1->1->2->3->4->4->5->6. Duplicates stay, and both an empty array and an array of empty lists should return null.

Intuition: don’t rescan all k heads every step

Merging two sorted lists is easy: compare the two front nodes, take the smaller, advance. The naive extension is to fold that across the array — merge list 0 with list 1, then merge that result with list 2, and so on. It works, but the accumulator keeps growing, so early nodes get walked again and again. With $n$ total nodes across $k$ lists, that’s $O(n \cdot k)$.

The wasted work is in finding the next smallest. At any moment the next output node is the minimum of the k current heads, and scanning all k of them every time is the expensive part. A min-heap answers “smallest head right now?” in $O(\log k)$ instead of $O(k)$. Each node enters and leaves the heap exactly once, so the total is:

$O(n \log k)$

Pairwise merging reaches the same bound from the other direction: merge lists in pairs so k lists become k/2, then k/4, and so on. There are $\log k$ rounds, and every round rewalks all $n$ nodes once — but only $\log k$ times total instead of the $k$ times the naive fold costs, which is exactly where $O(n \log k)$ comes from.

Solution

The heap version reads cleanly. Seed it with every non-null head, then repeatedly pull the smallest and push its successor:

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

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap =
            new PriorityQueue<>(Comparator.comparingInt(node -> node.val));

        // seed with the head of each list, skipping empty ones
        for (ListNode head : lists) {
            if (head != null) heap.offer(head);
        }

        ListNode dummy = new ListNode(0);   // dummy avoids a special case for the head
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode smallest = heap.poll();
            tail.next = smallest;           // reuse the node, don't allocate
            tail = smallest;
            if (smallest.next != null) heap.offer(smallest.next);
        }
        return dummy.next;
    }
}

If you’d rather avoid the heap import, divide-and-conquer is just the two-list merge applied to pairs of ranges:

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 - lo) / 2;
        ListNode left = merge(lists, lo, mid);
        ListNode right = merge(lists, mid + 1, hi);
        return mergeTwo(left, right);
    }

    private ListNode mergeTwo(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0), 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;   // attach whatever's left in one link
        return dummy.next;
    }
}

Complexity

Approach	Time	Space
Sequential merge (naive)	$O(k + n \cdot k)$	$O(1)$
Min-heap	$O(k + n \log(k{+}1))$	$O(k)$
Divide-and-conquer	$O(k + n \log(k{+}1))$	$O(\log k)$

The $O(k)$ term is the setup — every approach has to at least look at all k list heads, which is why an array of k empty lists still costs $\Theta(k)$ even though $n = 0$. The $\log(k{+}1)$ rather than $\log k$ is deliberate too: with a single list ($k = 1$) the heap version still offers and polls all $n$ nodes, so its per-node factor can’t collapse to zero. (Divide-and-conquer is the exception — it returns lists[0] in $O(1)$ when k = 1, never touching the nodes — so that bound is really the heap’s.) Past that, both optimal approaches share the runtime; they differ only in extra space — the heap holds k nodes, while divide-and-conquer spends $O(\log k)$ on the recursion stack.

In an interview

Say the naive plan out loud first — “I can fold merge-two across the array” — then name why it’s slow: the accumulator gets rewalked, giving $O(n \cdot k)$. That framing earns you the pivot to $O(n \log k)$ and shows you know where the cost lives. Pick the heap if you want the shorter code, or divide-and-conquer if you’d rather not reach for PriorityQueue; either is a fine answer as long as you can defend the complexity.

The trap is the empty input. An empty array, and an array like [[]] whose only list is null, both need to survive — the heap version handles them for free (nothing gets offered), but the recursive version needs the lists.length == 0 guard up top or it indexes out of bounds. This whole problem is really Merge Two Sorted Lists scaled up, so make sure that building block is airtight before you layer the heap on. The pattern hub collects the rest of the list family.

References

• LeetCode 23 — Merge k Sorted Lists