LeetCode 23: Merge k Sorted Lists

 Merge k Sorted Lists - LeetCode Solution (C++)

Merging multiple sorted linked lists is a common problem in coding interviews. We will explore different approaches, focusing on the optimal one.

---

Problem Statement

LeetCode 23: Merge k Sorted Lists

You are given an array of k linked lists, where 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]

Example 2:

Input:

lists = []

Output:

[]

Example 3:

Input:

lists = [[]]

Output:

[]

---

Optimal Approach - Min Heap (Priority Queue)

Key Idea

1. We use a Min Heap (Priority Queue) to always extract the smallest node among k lists.
2. Insert the head of each list into the Min Heap.
3. Extract the minimum element from the heap, add it to the merged list, and insert the next node of the extracted element.
4. Repeat until all nodes are merged.

Time Complexity:

• O(N log k) where N is the total number of nodes and k is the number of lists.
• Extracting from the min heap takes O(log k) and we do this N times.

Space Complexity:

• O(k) for the heap storage.

---

C++ Solution (LeetCode Compatible)

class Solution {
public:
    struct Compare {
        bool operator()(ListNode* a, ListNode* b) {
            return a->val > b->val;
        }
    };
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Compare> minHeap;
        
        for (auto list : lists) {
            if (list) minHeap.push(list);
        }
        
        ListNode* dummy = new ListNode(-1);
        ListNode* tail = dummy;
        
        while (!minHeap.empty()) {
            ListNode* node = minHeap.top();
            minHeap.pop();
            tail->next = node;
            tail = node;
            if (node->next) minHeap.push(node->next);
        }
        
        return dummy->next;
    }
};

---

Step-by-Step Code Explanation

1. Define a custom comparator inside a struct (Compare) to order the priority queue based on node values.
2. Initialize a min heap (priority_queue<ListNode*, vector<ListNode*>, Compare> minHeap;).
3. Push the head of each linked list into the heap.
4. Extract the smallest node and attach it to the merged list.
5. Push the next node from the extracted list into the heap.
6. Repeat until all nodes are processed.
7. Return the merged list starting from dummy->next.

---

Dry Run / Execution Steps

Input:

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

Heap State & Merged List

Step	Min Heap	Merged List
1	1, 1, 2	1 →
2	1, 2, 4	1 → 1 →
3	2, 4, 4	1 → 1 → 2 →
4	3, 4, 4	1 → 1 → 2 → 3 →
5	4, 4, 5	1 → 1 → 2 → 3 → 4 →
6	4, 5, 6	1 → 1 → 2 → 3 → 4 → 4 →
7	5, 6	1 → 1 → 2 → 3 → 4 → 4 → 5 →
8	6	1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 →
9	Empty	1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Final Output:

[1,1,2,3,4,4,5,6]

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Notes
Brute Force (Concatenate & Sort)	O(N log N)	O(N)	❌ Sorting overhead
Merge Two at a Time (Iterative Merging)	O(N log k)	O(1)	✅ Good, but slower than heap
Divide & Conquer (Recursive Merging)	O(N log k)	O(log k)	✅ Optimal alternative
Min Heap (Best Approach) ✅	O(N log k)	O(k)	✅ Efficient with priority queue

Why Min Heap is Best?

✔ Maintains sorted order efficiently.
✔ Merges k lists optimally using log operations.
✔ Handles large N values effectively.

---

Conclusion

• Best approach: Min Heap (Priority Queue)
• Why? Efficiently extracts the smallest element in O(log k) time.
• Alternative: Divide & Conquer for reduced space complexity.
• Practice More:
  • Merge Two Sorted Lists
  • Sort List
  • Merge Intervals

Would you like more detailed tutorials like this? Let me know! 🚀