Merge k Sorted Lists (LC 23)

Pattern: Heap (Min-Priority Queue) / Divide & Conquer
Difficulty: Hard
Key Concept: Always pick the smallest current head among k lists using a min-heap ordered by node value (tie-break by list id).

Problem Statement

You are given an array of k linked lists, each sorted in ascending order. Merge all lists into one sorted linked list.

Input: ListNode[] lists (may contain empty lists).
Output: Head of merged sorted list.

Example

lists = [1->4->5, 1->3->4, 2->6]
Merged: 1->1->2->3->4->4->5->6

---

1. Algorithm & Pseudocode

Brute force

1. Collect all node values into an ArrayList, sort, rebuild a new linked list — O(N log N) time, O(N) space, ignores original list structure until rebuild.

Pseudocode

vals = []
for each list head:
    walk list, push all vals to vals
sort(vals)
dummy = new node; cur = dummy
for v in vals: cur.next = new ListNode(v); cur = cur.next
return dummy.next

Optimal

1. Min-heap of size at most k: each entry (value, listId, node) or use ListNode with custom comparator.
2. Push all k heads.
3. While heap not empty: pop min n, append to result, if n.next push n.next.
4. Alternative: merge pairs of lists repeatedly — O(N log k) time, O(1) extra if merging in place (harder in Java).

Pseudocode (heap)

heap = min-heap of nodes by val
for each non-null head: heap.push(head)
dummy; tail = dummy
while heap not empty:
    n = heap.pop()
    tail.next = n; tail = n
    if n.next != null: heap.push(n.next)
return dummy.next

---

2. Step-by-Step Analysis (Beginner-Friendly)

• At any moment, the next smallest element must be one of the k current heads — comparing all k naively each step is O(k) per pop → O(Nk); heap makes each step O(log k).
• Why not merge two at a time only: Pairwise merge is also O(N log k) and uses less heap memory — both are interview-grade.
• Tie-breaking: If two nodes have same value, any consistent tie-break avoids comparator instability issues.

---

3. The Dry Run

Lists: A: 1→4, B: 1→3, C: 2

Min-heap (shows node values after each pop/push)

Step	Heap contents (values)	Pop	Append	Push next
init	{1a,1b,2}	—	—	heads
1	{1b,2,4}	1 from A	1	4
2	{2,3,4}	1 from B	1	3
3	{3,4}	2 from C	2	—
4	{4}	3	3	—
5	∅	4	4	—

ASCII (lists before merge)

A: 1 --> 4
B: 1 --> 3
C: 2

Merged: 1 --> 1 --> 2 --> 3 --> 4

---

4. Java Solution

Brute Force

import java.util.*;

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

class SolutionBrute {
    // Time: O(N log N), Space: O(N)
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> vals = new ArrayList<>();
        for (ListNode head : lists) {
            while (head != null) {
                vals.add(head.val);
                head = head.next;
            }
        }
        Collections.sort(vals);
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int v : vals) {
            cur.next = new ListNode(v);
            cur = cur.next;
        }
        return dummy.next;
    }
}

Optimal

import java.util.PriorityQueue;

class Solution {
    // Time: O(N log k), Space: O(k) heap (k lists)
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
                (a, b) -> Integer.compare(a.val, b.val));
        for (ListNode h : lists) {
            if (h != null) pq.offer(h);
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!pq.isEmpty()) {
            ListNode n = pq.poll();
            tail.next = n;
            tail = n;
            if (n.next != null) pq.offer(n.next);
        }
        return dummy.next;
    }
}

---

5. The “Java vs. Others” Edge

• PriorityQueue<ListNode> requires comparator; default uses Comparable — ListNode on LeetCode often does not implement it, so pass (a,b) -> Integer.compare(a.val, b.val).
• Null heads: skip when offering initial nodes.
• Pairwise merge: iterative merge of two lists k times is O(N log k) with O(1) extra heap — good if heap size is a concern.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute collect + sort	O(N log N)	O(N)	Loses pointer reuse; simple
Min-heap	O(N log k)	O(k)	k = number of lists
Divide & conquer merge	O(N log k)	O(log k) stack	Merge lists pairwise

N = total nodes across all lists.