284. Merge K Sorted Lists

🔗 LeetCode Problem: 23. Merge K Sorted Lists
📊 Difficulty: Hard
🏷️ Topics: Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort

Problem Statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints: - k == lists.length - 0 <= k <= 10^4 - 0 <= lists[i].length <= 500 - -10^4 <= lists[i][j] <= 10^4 - lists[i] is sorted in ascending order - The sum of lists[i].length will not exceed 10^4

---

🌟 Understanding the Problem

What are we merging?

We have k SORTED linked lists:
  List 1: 1 -> 4 -> 5
  List 2: 1 -> 3 -> 4
  List 3: 2 -> 6

Goal: Merge into ONE sorted list:
  Result: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Key Observations:

1. Each list is ALREADY sorted
   → Don't need to sort within a list
   → Just need to merge them

2. Similar to merging 2 sorted lists
   → But now we have k lists!
   → Need to find minimum among k heads

3. Total elements = sum of all list lengths
   → Let n = total elements
   → Final result has n nodes

4. Can solve multiple ways:
   → Brute force: Compare all heads each time
   → Better: Use min-heap
   → Optimal: Divide and conquer

---

🌟 The Natural Thinking Process

When you first see this problem:

Question: Merge k sorted lists

First Thought: "I know how to merge 2 sorted lists!"
  - Compare heads, pick smaller
  - Move pointer in that list
  - Repeat

"But with k lists, how do I find minimum among k heads?"

Natural evolution:
  1. Try all k heads each time (brute force)
  2. Use min-heap to find minimum efficiently
  3. Divide and conquer (merge pairs repeatedly)

The Evolution:

BRUTE FORCE THINKING:
  "At each step, scan all k list heads"
  "Pick minimum, add to result"
  Time: O(kn) - check k heads for each of n nodes
  Problem: Lots of repeated comparisons!
  ⬇

REALIZATION 1:
  "Finding minimum among k elements... min-heap!"
  "Heap can give minimum in O(log k)!"
  ⬇

OPTIMIZATION 1: Min-Heap
  "Keep all list heads in min-heap"
  "Extract min, add next node from that list"
  Time: O(n log k) - much better! ✨
  ⬇

REALIZATION 2:
  "Can I avoid heap operations?"
  "Merge 2 lists is O(n), very efficient"
  "What if I merge in pairs?"
  ⬇

OPTIMIZATION 2: Divide and Conquer
  "Merge pairs: k lists → k/2 → k/4 → ... → 1"
  "Each level merges all n nodes"
  Time: O(n log k) - same but simpler! ✨

---

🎯 Approach 1: Brute Force - Compare All Heads ⭐

The First Natural Solution

The Thought Process:

Step 1: At each step, scan all k list heads

Step 2: Find the minimum head

Step 3: Add minimum to result, advance that list

Step 4: Repeat until all lists exhausted

Simple but inefficient!

Visual Tracking - Complete Example

Input: lists = [[1,4,5], [1,3,4], [2,6]]

Initial state:
  List 0: 1 -> 4 -> 5
  List 1: 1 -> 3 -> 4
  List 2: 2 -> 6

═══════════════════════════════════════════════════════════════
STEP 1: Find minimum among all heads
═══════════════════════════════════════════════════════════════

Current heads:
  List 0: 1
  List 1: 1
  List 2: 2

Scan all: 1, 1, 2
Minimum: 1 (from List 0)

Action: Add 1 to result, advance List 0

Result: 1
Lists:
  List 0: 4 -> 5
  List 1: 1 -> 3 -> 4
  List 2: 2 -> 6

═══════════════════════════════════════════════════════════════
STEP 2: Find minimum among all heads
═══════════════════════════════════════════════════════════════

Current heads:
  List 0: 4
  List 1: 1
  List 2: 2

Scan all: 4, 1, 2
Minimum: 1 (from List 1)

Action: Add 1 to result, advance List 1

Result: 1 -> 1
Lists:
  List 0: 4 -> 5
  List 1: 3 -> 4
  List 2: 2 -> 6

═══════════════════════════════════════════════════════════════
STEP 3: Find minimum among all heads
═══════════════════════════════════════════════════════════════

Current heads:
  List 0: 4
  List 1: 3
  List 2: 2

Scan all: 4, 3, 2
Minimum: 2 (from List 2)

Action: Add 2 to result, advance List 2

Result: 1 -> 1 -> 2
Lists:
  List 0: 4 -> 5
  List 1: 3 -> 4
  List 2: 6

Continue this process...

═══════════════════════════════════════════════════════════════
FINAL RESULT
═══════════════════════════════════════════════════════════════

Result: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 ✓

Implementation

/**
 * Brute Force: Compare all k heads each time
 * Time: O(kn) where n = total nodes
 * Space: O(1)
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (true) {
            // Find minimum among all list heads
            int minIndex = -1;
            int minValue = Integer.MAX_VALUE;

            for (int i = 0; i < lists.length; i++) {
                if (lists[i] != null && lists[i].val < minValue) {
                    minValue = lists[i].val;
                    minIndex = i;
                }
            }

            // No more nodes
            if (minIndex == -1) break;

            // Add minimum to result
            current.next = lists[minIndex];
            current = current.next;

            // Advance that list
            lists[minIndex] = lists[minIndex].next;
        }

        return dummy.next;
    }
}

⏰ Time: O(kn) - For each of n nodes, scan k lists
💾 Space: O(1) - Only pointers

Why This is Inefficient:

Problem: Scans ALL k heads for EACH node!

Example: k = 100, n = 10,000
  Must do 100 comparisons for each of 10,000 nodes
  Total: 1,000,000 comparisons!

Most comparisons are wasted!
Can we find minimum faster?

---

💡 The First AHA Moment

OBSERVATION:

"I'm scanning k heads repeatedly to find minimum!"
"This is exactly what a min-heap is for!"

Min-heap can:
  - Store k elements
  - Give minimum in O(1)
  - Remove/add in O(log k)

Perfect for this problem! ✨

---

🎯 Approach 2: Min-Heap (Optimal with Heap) ⭐⭐⭐

The Better Solution

The Evolution of Thought:

Brute Force: Scan k heads each time
  ⬇
Observation: "Need efficient minimum finding!"
  ⬇
Pattern: "Min-heap for minimum among k elements!"
  ⬇
Better: "Min-heap of list heads!"

WHY Min-Heap Works - Complete Reasoning

The Core Question:

How does min-heap help merge k sorted lists?

Answer Through Detailed Reasoning:

PRINCIPLE 1: The Merging Strategy
═══════════════════════════════════════════════════════════════

Goal: Build result by always taking the SMALLEST available node

At any point:
  - Each list has a "head" (next node to consider)
  - Need to find MINIMUM among k heads
  - Add minimum to result
  - Advance that list

Brute force: O(k) to find minimum
Min-heap: O(log k) to find minimum ✓

═══════════════════════════════════════════════════════════════
PRINCIPLE 2: Min-Heap Strategy
═══════════════════════════════════════════════════════════════

Setup:
  Initialize heap with all k list heads
  Heap property: minimum always on top

Algorithm:
  1. Extract minimum from heap (the smallest head)
  2. Add it to result
  3. If that list has more nodes:
     - Add next node from that list to heap
  4. Repeat until heap empty

Why this works:
  - Heap always contains next candidates
  - Top of heap = global minimum among candidates
  - Each extraction is O(log k)
  - Each insertion is O(log k)

═══════════════════════════════════════════════════════════════
PRINCIPLE 3: Maintaining the Invariant
═══════════════════════════════════════════════════════════════

Invariant: Heap contains exactly one node from each non-empty list

Initially:
  Add first node of each list → k nodes in heap

After each extraction:
  Extracted node came from some list L
  Add next node from list L (if exists)
  Heap still has one node per non-empty list ✓

This ensures we always pick global minimum!

═══════════════════════════════════════════════════════════════
EXAMPLE: Why This Gives Correct Order
═══════════════════════════════════════════════════════════════

Lists:
  List A: 1 -> 4 -> 7
  List B: 2 -> 5 -> 8
  List C: 3 -> 6 -> 9

Heap initially: [1(A), 2(B), 3(C)]

Step 1: Extract 1
  Add to result: [1]
  Add next from A: 4
  Heap: [2(B), 3(C), 4(A)]

Step 2: Extract 2
  Add to result: [1, 2]
  Add next from B: 5
  Heap: [3(C), 4(A), 5(B)]

Step 3: Extract 3
  Add to result: [1, 2, 3]
  Add next from C: 6
  Heap: [4(A), 5(B), 6(C)]

And so on...
Always picking smallest available! ✓

═══════════════════════════════════════════════════════════════
WHY O(n log k)?
═══════════════════════════════════════════════════════════════

Total nodes: n

For each of n nodes:
  - Extract from heap: O(log k)
  - Maybe insert to heap: O(log k)

Total: O(n × log k) ✓

Much better than O(kn) brute force when k is large!

Example: k=100, n=10,000
  Brute force: 100 × 10,000 = 1,000,000
  Min-heap: 10,000 × log(100) ≈ 10,000 × 7 = 70,000
  14x faster! ✨

Visual Tracking - Complete Example

Input: lists = [[1,4,5], [1,3,4], [2,6]]

═══════════════════════════════════════════════════════════════
INITIALIZATION
═══════════════════════════════════════════════════════════════

Lists:
  List 0: 1 -> 4 -> 5
  List 1: 1 -> 3 -> 4
  List 2: 2 -> 6

Build min-heap with all heads:
  Heap: [1(L0), 1(L1), 2(L2)]
        ↑ top (minimum)

Result: []

═══════════════════════════════════════════════════════════════
STEP 1
═══════════════════════════════════════════════════════════════

Heap: [1(L0), 1(L1), 2(L2)]

Extract min: 1 from List 0
Add to result: [1]
Add next from List 0: 4

Heap after: [1(L1), 2(L2), 4(L0)]
            ↑ top

Result: 1

═══════════════════════════════════════════════════════════════
STEP 2
═══════════════════════════════════════════════════════════════

Heap: [1(L1), 2(L2), 4(L0)]

Extract min: 1 from List 1
Add to result: [1, 1]
Add next from List 1: 3

Heap after: [2(L2), 3(L1), 4(L0)]
            ↑ top

Result: 1 -> 1

═══════════════════════════════════════════════════════════════
STEP 3
═══════════════════════════════════════════════════════════════

Heap: [2(L2), 3(L1), 4(L0)]

Extract min: 2 from List 2
Add to result: [1, 1, 2]
Add next from List 2: 6

Heap after: [3(L1), 4(L0), 6(L2)]
            ↑ top

Result: 1 -> 1 -> 2

═══════════════════════════════════════════════════════════════
STEP 4
═══════════════════════════════════════════════════════════════

Heap: [3(L1), 4(L0), 6(L2)]

Extract min: 3 from List 1
Add to result: [1, 1, 2, 3]
Add next from List 1: 4

Heap after: [4(L0), 4(L1), 6(L2)]
            ↑ top (first 4)

Result: 1 -> 1 -> 2 -> 3

═══════════════════════════════════════════════════════════════
STEP 5
═══════════════════════════════════════════════════════════════

Heap: [4(L0), 4(L1), 6(L2)]

Extract min: 4 from List 0
Add to result: [1, 1, 2, 3, 4]
Add next from List 0: 5

Heap after: [4(L1), 5(L0), 6(L2)]
            ↑ top

Result: 1 -> 1 -> 2 -> 3 -> 4

═══════════════════════════════════════════════════════════════
STEP 6
═══════════════════════════════════════════════════════════════

Heap: [4(L1), 5(L0), 6(L2)]

Extract min: 4 from List 1
Add to result: [1, 1, 2, 3, 4, 4]
List 1 exhausted (no next)

Heap after: [5(L0), 6(L2)]
            ↑ top

Result: 1 -> 1 -> 2 -> 3 -> 4 -> 4

═══════════════════════════════════════════════════════════════
STEP 7
═══════════════════════════════════════════════════════════════

Heap: [5(L0), 6(L2)]

Extract min: 5 from List 0
Add to result: [1, 1, 2, 3, 4, 4, 5]
List 0 exhausted

Heap after: [6(L2)]
            ↑ top

Result: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5

═══════════════════════════════════════════════════════════════
STEP 8
═══════════════════════════════════════════════════════════════

Heap: [6(L2)]

Extract min: 6 from List 2
Add to result: [1, 1, 2, 3, 4, 4, 5, 6]
List 2 exhausted

Heap after: [] (empty)

Result: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 ✓

═══════════════════════════════════════════════════════════════
FINAL RESULT
═══════════════════════════════════════════════════════════════

Result: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 ✓

Operations:
  - 8 extractions (one per node)
  - 8 insertions (heads + next nodes)
  - All O(log 3) each

Total: O(8 × log 3) ≈ O(n log k) ✓

Implementation

import java.util.*;

/**
 * Min-Heap Solution
 * Time: O(n log k) where n = total nodes, k = number of lists
 * Space: O(k) for heap
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // Min-heap by node value
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare(a.val, b.val)
        );

        // Add all list heads to heap
        for (ListNode head : lists) {
            if (head != null) {
                minHeap.offer(head);
            }
        }

        // Build result
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (!minHeap.isEmpty()) {
            // Extract minimum
            ListNode minNode = minHeap.poll();

            // Add to result
            current.next = minNode;
            current = current.next;

            // Add next from same list
            if (minNode.next != null) {
                minHeap.offer(minNode.next);
            }
        }

        return dummy.next;
    }
}

⏰ Time: O(n log k)
💾 Space: O(k)

Why This is Better:

✓ O(n log k) vs O(kn) brute force
✓ Efficient minimum finding
✓ Heap size never exceeds k

Example: k=100, n=10,000
  Brute: 1,000,000 ops
  Heap: 70,000 ops
  14x faster! ✨

---

💡 The Second AHA Moment

OBSERVATION:

"Min-heap is O(n log k), pretty good!"
"But I know merging 2 sorted lists is very efficient..."
"What if I merge lists in pairs?"

Divide and conquer approach:
  Round 1: k lists → k/2 merged lists
  Round 2: k/2 lists → k/4 merged lists
  ...
  Final: 1 merged list

Let me explore this...

---

🎯 Approach 3: Divide and Conquer (Optimal) ⭐⭐⭐

The Optimal Solution

The Evolution of Thought:

Brute force: O(kn)
  ⬇
Min-heap: O(n log k)
  ⬇
Observation: "Merge 2 lists is O(n), very clean!"
  ⬇
Idea: "Merge in pairs repeatedly!"
  ⬇
Optimal: "Divide and conquer!"

Understanding Divide and Conquer - Complete Explanation

How does this work?

DIVIDE AND CONQUER CONCEPT:

Instead of merging k lists at once,
merge them in pairs repeatedly!

Strategy:
  Round 1: Merge pairs → k lists become k/2 lists
  Round 2: Merge pairs → k/2 lists become k/4 lists
  Round 3: Merge pairs → k/4 lists become k/8 lists
  ...
  Final: 2 lists become 1 list

Number of rounds: log k

Each round: Merges all n total nodes
  Time per round: O(n)

Total: O(n log k) ✓

Same complexity as heap, but simpler logic!

WHY Divide and Conquer Works - Detailed Reasoning

The Core Question:

Why is merging in pairs better than merging all at once?

Answer Through Reasoning:

PRINCIPLE 1: Merge 2 Lists is Efficient
═══════════════════════════════════════════════════════════════

Merging 2 sorted lists:
  - Compare heads, pick smaller
  - Simple, clean, O(n1 + n2)
  - Very efficient!

Merging k lists directly:
  - Need to find min among k heads
  - More complex
  - Needs heap or repeated scanning

Idea: Use efficient 2-list merge as building block!

═══════════════════════════════════════════════════════════════
PRINCIPLE 2: Pairing Strategy
═══════════════════════════════════════════════════════════════

Example: k = 4 lists
  Lists: [L0, L1, L2, L3]

Round 1: Merge pairs
  Merge L0 + L1 → M0
  Merge L2 + L3 → M1
  Result: [M0, M1]

Round 2: Merge pairs
  Merge M0 + M1 → Final
  Result: [Final]

Total rounds: log₂(4) = 2 ✓

═══════════════════════════════════════════════════════════════
PRINCIPLE 3: Work Analysis
═══════════════════════════════════════════════════════════════

Let n = total nodes across all lists

Round 1: Merge k lists (size n/k each) into k/2 lists
  Each merge: 2 × (n/k) = 2n/k nodes
  Number of merges: k/2
  Total work: (k/2) × (2n/k) = n ✓

Round 2: Merge k/2 lists into k/4 lists
  Each merge: 2 × (2n/k) = 4n/k nodes
  Number of merges: k/4
  Total work: (k/4) × (4n/k) = n ✓

Pattern: Each round does O(n) work!

Number of rounds: log k

Total: O(n × log k) ✓

═══════════════════════════════════════════════════════════════
VISUAL EXAMPLE
═══════════════════════════════════════════════════════════════

k = 8 lists, each with n/8 nodes

Round 1: 8 → 4
  [L0, L1, L2, L3, L4, L5, L6, L7]
  Merge pairs:
    L0+L1=M0, L2+L3=M1, L4+L5=M2, L6+L7=M3
  Result: [M0, M1, M2, M3]
  Work: 4 merges × (2n/8) = n

Round 2: 4 → 2
  [M0, M1, M2, M3]
  Merge pairs:
    M0+M1=N0, M2+M3=N1
  Result: [N0, N1]
  Work: 2 merges × (4n/8) = n

Round 3: 2 → 1
  [N0, N1]
  Merge pairs:
    N0+N1=Final
  Result: [Final]
  Work: 1 merge × (8n/8) = n

Total rounds: 3 = log₂(8)
Total work: 3n = O(n log k) ✓

═══════════════════════════════════════════════════════════════
WHY THIS IS ELEGANT
═══════════════════════════════════════════════════════════════

Advantages over heap approach:
  ✓ Uses simple 2-list merge (clean code)
  ✓ No heap data structure needed
  ✓ Same O(n log k) complexity
  ✓ Better cache locality
  ✓ Easier to understand

Same complexity, simpler implementation! ✨

Visual Tracking - Complete Example

Input: lists = [[1,4,5], [1,3,4], [2,6], [0,7]]

k = 4 lists, need log₂(4) = 2 rounds

═══════════════════════════════════════════════════════════════
INITIAL STATE
═══════════════════════════════════════════════════════════════

Lists:
  L0: 1 -> 4 -> 5
  L1: 1 -> 3 -> 4
  L2: 2 -> 6
  L3: 0 -> 7

═══════════════════════════════════════════════════════════════
ROUND 1: Merge pairs (4 → 2)
═══════════════════════════════════════════════════════════════

Pair 1: Merge L0 and L1
  L0: 1 -> 4 -> 5
  L1: 1 -> 3 -> 4

  Merge process:
    Compare: 1 vs 1 → take 1 from L0
    Compare: 4 vs 1 → take 1 from L1
    Compare: 4 vs 3 → take 3 from L1
    Compare: 4 vs 4 → take 4 from L0
    Compare: 5 vs 4 → take 4 from L1
    Take: 5 from L0

  M0: 1 -> 1 -> 3 -> 4 -> 4 -> 5

Pair 2: Merge L2 and L3
  L2: 2 -> 6
  L3: 0 -> 7

  Merge process:
    Compare: 2 vs 0 → take 0 from L3
    Compare: 2 vs 7 → take 2 from L2
    Compare: 6 vs 7 → take 6 from L2
    Take: 7 from L3

  M1: 0 -> 2 -> 6 -> 7

After Round 1:
  Lists: [M0, M1]
  M0: 1 -> 1 -> 3 -> 4 -> 4 -> 5
  M1: 0 -> 2 -> 6 -> 7

═══════════════════════════════════════════════════════════════
ROUND 2: Merge pairs (2 → 1)
═══════════════════════════════════════════════════════════════

Pair 1: Merge M0 and M1
  M0: 1 -> 1 -> 3 -> 4 -> 4 -> 5
  M1: 0 -> 2 -> 6 -> 7

  Merge process:
    Compare: 1 vs 0 → take 0 from M1
    Compare: 1 vs 2 → take 1 from M0
    Compare: 1 vs 2 → take 1 from M0
    Compare: 3 vs 2 → take 2 from M1
    Compare: 3 vs 6 → take 3 from M0
    Compare: 4 vs 6 → take 4 from M0
    Compare: 4 vs 6 → take 4 from M0
    Compare: 5 vs 6 → take 5 from M0
    Take: 6 from M1
    Take: 7 from M1

  Final: 0 -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> 7

═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════

Final merged list:
  0 -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> 7 ✓

Complexity:
  Total nodes: n = 10
  Rounds: log₂(4) = 2
  Work per round: O(10)
  Total: O(10 × 2) = O(n log k) ✓

Implementation with Detailed Code Walkthrough

Two versions: Recursive (clearer) and Iterative (optimal)

Version 1: Recursive (Most Intuitive)

/**
 * Divide and Conquer - Recursive
 * Time: O(n log k)
 * Space: O(log k) for recursion stack
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // Divide and conquer: merge range [left, right]
        return mergeRange(lists, 0, lists.length - 1);
    }

    /**
     * Merge lists in range [left, right] using divide and conquer
     * 
     * @param lists - array of list heads
     * @param left - left index of range
     * @param right - right index of range
     * @return merged list of range [left, right]
     */
    private ListNode mergeRange(ListNode[] lists, int left, int right) {
        // Base case: single list
        if (left == right) {
            return lists[left];
        }

        // Base case: two lists
        if (left + 1 == right) {
            return merge2Lists(lists[left], lists[right]);
        }

        // Recursive case: divide into two halves
        int mid = left + (right - left) / 2;

        ListNode leftMerged = mergeRange(lists, left, mid);
        ListNode rightMerged = mergeRange(lists, mid + 1, right);

        return merge2Lists(leftMerged, rightMerged);
    }

    /**
     * Merge 2 sorted linked lists
     * Classic two-pointer merge
     * 
     * @param l1 - first sorted list
     * @param l2 - second sorted list
     * @return merged sorted list
     */
    private ListNode merge2Lists(ListNode l1, ListNode l2) {
        // Dummy node simplifies edge cases
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // Merge while both lists have nodes
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // Append remaining nodes (at most one list has remaining)
        current.next = (l1 != null) ? l1 : l2;

        return dummy.next;
    }
}

Code Walkthrough with Example:

Input: lists = [L0, L1, L2, L3] (4 lists)

mergeKLists(lists):
  Call mergeRange(lists, 0, 3)

mergeRange(lists, 0, 3):
  left=0, right=3, mid=1

  Left half: mergeRange(lists, 0, 1)
    left=0, right=1 (two lists)
    Return merge2Lists(L0, L1) → M0

  Right half: mergeRange(lists, 2, 3)
    left=2, right=3 (two lists)
    Return merge2Lists(L2, L3) → M1

  Final: merge2Lists(M0, M1) → Result ✓

Recursion tree:
                    [L0,L1,L2,L3]
                   /              \
            [L0,L1]                [L2,L3]
            /     \                /     \
          L0      L1             L2      L3
           \     /                \     /
            M0                      M1
             \                     /
                   Final Result

Height of tree: log₂(4) = 2
Work per level: O(n)
Total: O(n log k) ✓

Version 2: Iterative (Space Optimal)

/**
 * Divide and Conquer - Iterative
 * Time: O(n log k)
 * Space: O(1) auxiliary
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        int k = lists.length;

        // Merge in pairs, doubling interval each round
        // interval represents the "gap" between pairs
        int interval = 1;

        while (interval < k) {
            // Merge pairs at distance 'interval'
            for (int i = 0; i + interval < k; i += interval * 2) {
                lists[i] = merge2Lists(lists[i], lists[i + interval]);
            }
            interval *= 2;
        }

        return lists[0];
    }

    /**
     * Merge 2 sorted linked lists
     */
    private ListNode merge2Lists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

Iterative Code Walkthrough:

Input: lists = [L0, L1, L2, L3, L4, L5, L6, L7] (k=8)

═══════════════════════════════════════════════════════════════
ROUND 1: interval = 1 (merge adjacent pairs)
═══════════════════════════════════════════════════════════════

Loop: i goes 0, 2, 4, 6 (step = interval * 2 = 2)

i=0: Merge lists[0] and lists[1]
  lists[0] = merge2Lists(L0, L1) → M0

i=2: Merge lists[2] and lists[3]
  lists[2] = merge2Lists(L2, L3) → M1

i=4: Merge lists[4] and lists[5]
  lists[4] = merge2Lists(L4, L5) → M2

i=6: Merge lists[6] and lists[7]
  lists[6] = merge2Lists(L6, L7) → M3

After Round 1:
  lists = [M0, L1, M1, L3, M2, L5, M3, L7]
           ↑        ↑        ↑        ↑
      positions 0, 2, 4, 6 have merged results

═══════════════════════════════════════════════════════════════
ROUND 2: interval = 2 (merge pairs at distance 2)
═══════════════════════════════════════════════════════════════

Loop: i goes 0, 4 (step = interval * 2 = 4)

i=0: Merge lists[0] and lists[2]
  lists[0] = merge2Lists(M0, M1) → N0

i=4: Merge lists[4] and lists[6]
  lists[4] = merge2Lists(M2, M3) → N1

After Round 2:
  lists = [N0, L1, M1, L3, N1, L5, M3, L7]
           ↑                 ↑
      positions 0, 4 have merged results

═══════════════════════════════════════════════════════════════
ROUND 3: interval = 4 (merge pairs at distance 4)
═══════════════════════════════════════════════════════════════

Loop: i goes 0 (step = interval * 2 = 8)

i=0: Merge lists[0] and lists[4]
  lists[0] = merge2Lists(N0, N1) → Final

After Round 3:
  lists = [Final, L1, M1, L3, N1, L5, M3, L7]
           ↑
      position 0 has final merged result

interval = 8, loop exits (8 >= k)

Return lists[0] = Final ✓

═══════════════════════════════════════════════════════════════

Key insight:
  interval doubles each round: 1 → 2 → 4 → 8
  Number of rounds: log₂(8) = 3
  Each round merges all n nodes
  Total: O(n × 3) = O(n log k) ✓

Visual Comparison of Both Versions:

Recursive:
  Pros:
    ✓ More intuitive (clear divide and conquer)
    ✓ Easier to understand
    ✓ Matches mental model

  Cons:
    ✗ O(log k) recursion stack space
    ✗ Function call overhead

Iterative:
  Pros:
    ✓ O(1) space (optimal!)
    ✓ No recursion overhead
    ✓ Better for production

  Cons:
    ✗ Less intuitive initially
    ✗ Interval logic requires thought

Recommendation:
  Interview: Start with recursive (clearer)
  Production: Use iterative (optimal space)

⏰ Time: O(n log k) - Both versions
💾 Space: - Recursive: O(log k) for call stack - Iterative: O(1) auxiliary

Why This is Elegant:

✓ Same O(n log k) as heap approach
✓ Uses simple 2-list merge as building block
✓ Iterative version has O(1) space (better than heap's O(k))
✓ Better cache locality than heap
✓ Recursive version very clear
✓ Iterative version space-optimal

Two versions for different needs:
  - Recursive: Clarity in interviews
  - Iterative: Optimal in production

Clean and optimal! ✨

---

📊 Approach Comparison

┌──────────────────┬─────────────┬──────────┬─────────────────┐
│ Approach         │ Time        │ Space    │ Key Insight     │
├──────────────────┼─────────────┼──────────┼─────────────────┤
│ Brute Force      │ O(kn)       │ O(1)     │ Scan all heads  │
│ Min-Heap         │ O(n log k)  │ O(k)     │ Efficient min   │
│ Divide & Conquer │ O(n log k)  │ O(1)     │ Merge in pairs  │
└──────────────────┴─────────────┴──────────┴─────────────────┘

n = total nodes, k = number of lists

---

💡 Key Learnings

1. PATTERN RECOGNITION:
   ✓ Merge k sorted → min-heap OR divide & conquer
   ✓ Similar to merge sort concept

2. MIN-HEAP FOR K-WAY MERGE:
   ✓ Keep k candidates in heap
   ✓ Extract min in O(log k)
   ✓ Perfect for k-way merge

3. DIVIDE AND CONQUER:
   ✓ Use efficient 2-way merge
   ✓ Merge pairs repeatedly
   ✓ log k rounds, O(n) work each

4. COMPLEXITY ANALYSIS:
   ✓ Brute: O(kn) - too slow
   ✓ Optimal: O(n log k) - both heap and D&C
   ✓ D&C has better space: O(1) vs O(k)

---

⚠️ Common Mistakes

// Mistake 1: Not handling null lists
for (ListNode head : lists) {
    minHeap.offer(head);  // ❌ May add null!
}

// ✓ CORRECT
for (ListNode head : lists) {
    if (head != null) {
        minHeap.offer(head);
    }
}

// Mistake 2: Wrong heap comparator
PriorityQueue<ListNode> heap = new PriorityQueue<>();  
// ❌ Compares ListNode objects, not values!

// ✓ CORRECT
PriorityQueue<ListNode> heap = new PriorityQueue<>(
    (a, b) -> Integer.compare(a.val, b.val)
);

// Mistake 3: Forgetting to add next node
ListNode min = heap.poll();
current.next = min;
// ❌ Forgot to add min.next to heap!

// ✓ CORRECT
ListNode min = heap.poll();
current.next = min;
if (min.next != null) {
    heap.offer(min.next);
}

---

📝 Quick Revision

🎯 Core: Merge k sorted lists. Brute: O(kn) scan all heads. Min-heap: O(n log k), keep k heads in heap. D&C: O(n log k), merge pairs repeatedly. Both optimal approaches are O(n log k)!

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

class ListNode {
  int val;
  ListNode next;

  ListNode() {
  }

  ListNode(int val) {
    this.val = val;
  }

  ListNode(int val, ListNode next) {
    this.val = val;
    this.next = next;
  }
}

public class Solution {
  public static ListNode create(List<Integer> list) {
    ListNode dummy = new ListNode(-1);
    ListNode curr = dummy;

    for (int num : list) {
      curr.next = new ListNode(num);
      curr = curr.next;
    }

    return dummy.next;
  }

  public static void print(ListNode head) {
    ListNode curr = head;
    while (curr != null) {
      System.out.print(curr.val + " -> ");
      curr = curr.next;
    }

    System.out.println();
  }

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

    if (lists.length == 1) {
      return lists[0];
    }

    // return naive(lists);
    // return minHeap(lists);
    return mergeSort(lists, 0, lists.length - 1);
  }

  private ListNode mergeSort(ListNode[] lists, int left, int right) {
    // step 1: we need to merge sort in the range [left, right]

    // step 2: base case 1 - done with the current partition
    if (left == right) {
      return lists[left];
    }

    // step 3: base case 2 - we are left with only 2 lists left
    if (left + 1 == right) {
      return merge2Lists(lists[left], lists[right]);
    }

    // step 4: divide and conquer
    int mid = right + (left - right) / 2;
    ListNode leftPartition = mergeSort(lists, left, mid);
    ListNode rightPartition = mergeSort(lists, mid + 1, right);

    return merge2Lists(leftPartition, rightPartition);
  }

  private ListNode merge2Lists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);
    ListNode currNode = dummy;

    // case 1: still elements left in both lists
    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        currNode.next = new ListNode(l1.val);
        currNode = currNode.next;

        l1 = l1.next;
      } else {
        currNode.next = new ListNode(l2.val);
        currNode = currNode.next;

        l2 = l2.next;
      }
    }

    // case 2: still elements left in l1
    while (l1 != null) {
      currNode.next = new ListNode(l1.val);
      currNode = currNode.next;

      l1 = l1.next;
    }

    // case 3: still elements left in l2
    while (l2 != null) {
      currNode.next = new ListNode(l2.val);
      currNode = currNode.next;

      l2 = l2.next;
    }

    return dummy.next;
  }

  private ListNode minHeap(ListNode[] lists) {
    // step 1: create a dummy node
    ListNode dummy = new ListNode(-1);
    ListNode currNode = dummy;

    // step 2: create a min heap that always gives min element
    PriorityQueue<ListNode> pq = new PriorityQueue<>((node1, node2) -> node1.val - node2.val);

    // step 3: fill out PQ initially with all heads of all linked lists
    for (int i = 0; i < lists.length; i++) {
      if (lists[i] != null) {
        pq.offer(lists[i]);
      }
    }

    // step 3: loop till becomes empty
    while (!pq.isEmpty()) {
      // step 4: this gives min element currently present in PQ.
      ListNode polled = pq.poll();

      // step 5: append current min to list
      currNode.next = new ListNode(polled.val);
      currNode = currNode.next;

      // step 6: move min node pointer to next node
      if (polled.next != null) {
        pq.offer(polled.next);
      }
    }

    return dummy.next;
  }

  private ListNode naive(ListNode[] lists) {
    // step 1: create a dummy node
    ListNode dummy = new ListNode(-1);
    ListNode currNode = dummy;

    // step 2: run an infinite loop till all lists get empty
    while (true) {
      // step 3: initialize min (which also determines
      // if no more processing)
      int minVal = Integer.MAX_VALUE;
      int minNodeIndex = -1;

      // step 4: get min by checking current heads of all lists
      for (int i = 0; i < lists.length; i++) {
        if (lists[i] != null && lists[i].val < minVal) {
          minVal = lists[i].val;
          minNodeIndex = i;
        }
      }

      // step 5: check minNode to see if we are done
      // if its null, all lists are done processing and
      // break out of this infinite loop.
      if (minNodeIndex == -1) {
        break;
      }

      // step 6: append current min to list
      currNode.next = new ListNode(minVal);
      currNode = currNode.next;

      // step 7: move min node pointer to next node
      lists[minNodeIndex] = lists[minNodeIndex].next;
    }

    return dummy.next;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    ListNode list1 = create(Arrays.asList(1, 4, 5));
    ListNode list2 = create(Arrays.asList(1, 3, 4));
    ListNode list3 = create(Arrays.asList(2, 6));
    print(s.mergeKLists(new ListNode[] { list1, list2, list3 }));
    print(s.mergeKLists(new ListNode[] {}));
  }
}

🔑 Key: Min-heap for k-way merge. D&C merges in pairs. Both O(n log k). ✨

---

Happy practicing! 🎯💪✨

Note: This problem demonstrates k-way merge pattern using min-heap! You learn: (1) WHY min-heap for finding minimum among k elements, (2) Divide and conquer alternative with same complexity, (3) Pattern appears in external sorting, streaming data merge, etc. Both approaches optimal O(n log k) - choose based on preference! True mastery! 💪✨🏆