Merge k Sorted Lists

• Difficulty: Hard
• Topics: Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort
• Link: https://leetcode.com/problems/merge-k-sorted-lists/

Problem Description

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 <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.

Solution

1. Problem Deconstruction

Rewrite the Problem

1. Technical Version:
   Given an array lists containing k singly-linked lists, where each list is sorted in non-decreasing order, merge all lists into a single sorted linked list by combining nodes. Constraints:

   • 0 ≤ k ≤ 10^4
   • Each list has 0–500 nodes
   • Node values ∈ [-10^4, 10^4]
   • Total nodes N ≤ 10^4
     Solution must efficiently handle edge cases (empty lists, empty sublists).

2. Beginner Version:
   You have several sorted chains of numbered blocks. Each chain is arranged from smallest to largest. Combine all chains into one long sorted chain by always picking the smallest available block from the front of any chain.

3. Mathematical Version:
   Let L = [L₁, L₂, ..., Lₖ] be an array of k sorted linked lists. Define:

   • head(Lᵢ) = first node of list i
   • val(n) = value of node n
   • next(n) = subsequent node of n
     Produce merged list M such that:
   • M contains all nodes from all Lᵢ
   • For any consecutive nodes Mⱼ, Mⱼ₊₁ in M, val(Mⱼ) ≤ val(Mⱼ₊₁)
   • Total nodes N = Σ|Lᵢ| ≤ 10^4

Constraint Analysis

1. 0 <= k <= 10^4:

   • Limits algorithms to ≤ O(k) space.
   • Edge: k=0 → return empty list.
   • Worst-case k=10^4 prohibits O(k)-per-node operations (→ O(kN) = 100e6 ops, borderline in Python).

2. 0 <= lists[i].length <= 500:

   • Individual lists may be empty → must skip during processing.
   • Total N ≤ 10^4 ensures O(N log k) is efficient (≈133k ops for k=10^4).

3. -10^4 <= lists[i][j] <= 10^4:

   • Values are bounded integers but merging is comparison-based; non-comparison sorts (e.g., counting) are impractical due to linked-list structure.

4. Sorted Order:

   • Critical for efficient merging; only heads need comparison.
   • Edge: All lists empty → return [].

5. Total Nodes N ≤ 10^4:

   • Permits O(N log N) solutions (130k ops) but O(N log k) is optimal.
   • Hidden edge: Many empty lists (e.g., k=10^4, only 1 list non-empty).

---

2. Intuition Scaffolding

Analogies

1. Real-World Metaphor:
   Multiple airport security lines sorted by passenger priority. Guards repeatedly admit the highest-priority passenger from any front, updating their line.

2. Gaming Analogy:
   In an RPG, merge loot from k sorted treasure piles. At each turn, pick the smallest-value item from any pile to optimize inventory.

3. Math Analogy:
   Iteratively find the minimum value in k sorted sequences, equivalent to maintaining a min-heap over k elements.

Common Pitfalls

1. Brute-Force Comparison (O(kN)):
   Scanning all k heads for each node → 100e6 ops for k=N=10^4 → slow in Python.
2. Ignoring Empty Lists:
   Accessing None.val causes crashes.
3. Global Sort Without Pointers:
   Collecting all values → O(N log N) time, O(N) space, but wastes sorted-list information.
4. Heap Tie-Breaking Errors:
   Pushing (val, node) without tie-breaker → Python crashes when val equal and nodes compared.
5. Divide-and-Conquer Recursion Depth:
   Unbalanced merging → unnecessary stack overhead.

---

3. Approach Encyclopedia

Approach 1: Brute-Force Comparison

Pseudocode:

def mergeKLists(lists):  
    dummy = curr = ListNode(0)  
    while True:  
        min_node, min_idx = None, -1  
        for i, node in enumerate(lists):  
            if node and (min_node is None or node.val < min_node.val):  
                min_node, min_idx = node, i  
        if min_idx == -1: break  
        curr.next = min_node  
        curr = curr.next  
        lists[min_idx] = min_node.next  # Advance chosen list  
    return dummy.next  

Complexity Proof:

• Time: O(kN) — For each of N nodes, scan k lists → worst-case 10^4 * 10^4 = 10^8 ops.
• Space: O(1) — No extra data structures.

Visualization:

Initial: 
  lists = [[1→4→5], [1→3→4], [2→6]]
Step 1: Min=1 (list0) → merged=[1], lists[0]=4→5
Step 2: Min=1 (list1) → merged=[1→1], lists[1]=3→4
Step 3: Min=2 (list2) → merged=[1→1→2], lists[2]=6
... 
Output: 1→1→2→3→4→4→5→6

Approach 2: Min-Heap (Priority Queue)

Pseudocode:

import heapq  
def mergeKLists(lists):  
    heap = []  
    for i, node in enumerate(lists):  
        if node:  
            heapq.heappush(heap, (node.val, i, node))  # (val, idx, node)  
    dummy = curr = ListNode(0)  
    while heap:  
        val, idx, node = heapq.heappop(heap)  
        curr.next = node  
        curr = curr.next  
        if node.next:  
            heapq.heappush(heap, (node.next.val, idx, node.next))  
    return dummy.next  

Complexity Proof:

• Time: O(N log k) — Each of N nodes inserted/extracted once from heap of size ≤ k. Operations cost O(log k).
• Space: O(k) — Heap stores ≤ k nodes.

Visualization:

Heap state after each pop (simplified):
  Init: [(1,0,node0), (1,1,node1), (2,2,node2)]
  Pop (1,0): merged=[1] → push (4,0)
  Heap: [(1,1,node1), (2,2,node2), (4,0,node0)]
  Pop (1,1): merged=[1→1] → push (3,1)
  Heap: [(2,2), (3,1), (4,0)] ...

Approach 3: Divide and Conquer

Pseudocode:

def mergeTwoLists(l1, l2):  # Classic merge
    dummy = curr = ListNode(0)  
    while l1 and l2:  
        if l1.val < l2.val:  
            curr.next, l1 = l1, l1.next  
        else:  
            curr.next, l2 = l2, l2.next  
        curr = curr.next  
    curr.next = l1 or l2  
    return dummy.next  

def mergeKLists(lists):  
    if not lists: return None  
    while len(lists) > 1:  
        new_lists = []  
        for i in range(0, len(lists), 2):  
            if i+1 < len(lists):  
                new_lists.append(mergeTwoLists(lists[i], lists[i+1]))  
            else:  
                new_lists.append(lists[i])  
        lists = new_lists  
    return lists[0]  

Complexity Proof:

• Time: O(N log k) — Each pass merges all pairs (O(N) work per pass), log k passes.
• Space: O(1) — Iterative merging; O(log k) recursion depth if recursive.

Visualization:

Step 0: [[1→4→5], [1→3→4], [2→6]]
Step 1: Merge pair0: [1→4→5] & [1→3→4] → [1→1→3→4→4→5]; leave [2→6]
        lists = [[1→1→3→4→4→5], [2→6]]
Step 2: Merge [1→1→3→4→4→5] & [2→6] → [1→1→2→3→4→4→5→6]

---

4. Code Deep Dive

Optimal Solution (Min-Heap):

import heapq
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        # Push initial nodes (What): Non-empty list heads with (val, idx, node)
        # Why: Avoid scanning all heads repeatedly. Tie-breaker `idx` prevents node comparison errors.
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))
        
        dummy = curr = ListNode(0)  # Dummy head for merged list
        while heap:
            val, idx, node = heapq.heappop(heap)  # Get smallest node
            curr.next = node  # Append to merged list
            curr = curr.next
            if node.next:  # Push next node from the same list
                heapq.heappush(heap, (node.next.val, idx, node.next))
        return dummy.next

Edge Case Handling:

• lists = []: Loop bypassed → return dummy.next = None.
• lists = [[]]: if node skips empty list → heap empty → return None.
• val duplicates: Tuple (val, idx, node) breaks ties with idx → no node comparison.
• Partial emptiness: Non-empty lists pushed initially; exhausted lists auto-ignored.

---

5. Complexity War Room

Hardware-Aware Analysis:

• Heap operations for N=10^4, k=10^4:
  • Heap size ≤ 10^4 → fits in CPU cache (240 KB for 24-byte tuples).
  • O(N log k) = 10^4 × log₂(10^4) ≈ 133k ops → <1ms in C++, ~10ms in Python.

Approach Comparison:

Approach	Time	Space	Readability	Interview Viability
Brute-Force	O(kN)	O(1)	9/10	❌ Fails large k
Min-Heap	O(N log k)	O(k)	8/10	✅ Optimal
Divide & Conquer	O(N log k)	O(1)	7/10	✅ Space-efficient
Global Sort	O(N log N)	O(N)	10/10	⚠️ Wastes sortedness

---

6. Pro Mode Extras

Variants:

1. Merge k Sorted Arrays:

   def merge_k_arrays(arrays):
       heap = []
       for i, arr in enumerate(arrays):
           if arr: 
               heapq.heappush(heap, (arr[0], i, 0))
       # Pop, then push next element from same array
   

   Complexity: O(N log k), same as linked lists.

2. External Merge (Huge k):
   Use min-heap with disk-backed priority queue. Complexity remains O(N log k) but I/O-optimized.

Interview Cheat Sheet:

• First Mention: Brute-force → heap/divide-conquer optimizations.
• Key Insight: Leverage sortedness; only heads are candidates.
• Edge Cases: k=0, all lists empty, one list non-empty.
• Python Nuance: Heap tuples require tie-breaker (e.g., idx) for nodes.
• Tradeoffs: Heap for simplicity, divide-conquer for O(1) space.