Merge K Sorted Lists Solution for Microsoft
Company: Microsoft · Difficulty: Hard · Topics: Linked List, Heap, Divide and Conquer
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.
Examples
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: Merging the three sorted lists gives us a sorted list.
Example 2:
Input: lists = []
Output: []
Explanation: Empty input returns empty list.
Example 3:
Input: lists = [[]]
Output: []
Explanation: Single empty list returns empty list.
Example 4:
Input: lists = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,4,5,6,7,8,9]
Explanation: Three separate sorted lists merge into one.
Example 5:
Input: lists = [[1],[2],[3]]
Output: [1,2,3]
Explanation: Single element lists merge in order.
Intuition
The key insight is that we need to efficiently merge multiple sorted lists. We can use a min-heap to always pick the smallest element from all the current heads of the lists. This ensures we build the final sorted list efficiently.
Approach
Approach 1: Min Heap (Optimal)
1. Create a min-heap and add the first node from each non-empty list
2. While heap is not empty:
- Extract the minimum node from heap
- Add it to the result list
- If the extracted node has a next node, add it to the heap
3. Return the merged list
Approach 2: Divide and Conquer
1. Merge lists in pairs recursively
2. Continue until only one list remains
3. This reduces the problem to merging two lists at a time
Approach 3: Brute Force
1. Collect all values from all lists
2. Sort the collected values
3. Create a new linked list from sorted values
Dry Run
Let's trace through Example 1: lists = [[1,4,5],[1,3,4],[2,6]]
Min Heap Approach:
- Initial heap: [1,1,2] (first elements from each list)
- Extract 1: result=[1], heap=[1,2,4] (add next from list 1)
- Extract 1: result=[1,1], heap=[2,3,4] (add next from list 2)
- Extract 2: result=[1,1,2], heap=[3,4,6] (add next from list 3)
- Continue until all elements are processed
Solution
Note: This solution provides multiple approaches to solve the problem. Choose the one that best fits your understanding and requirements.
Key Insights:
1. Min Heap: Always pick the smallest element from all current heads
2. Divide and Conquer: Reduce complexity by merging in pairs
3. Brute Force: Simple but less efficient for large inputs
Edge Cases:
- Empty input array: return null
- Array with empty lists: return null
- Single list: return the list as is
- Lists with different lengths: handle gracefully
Time Complexity
- Min Heap: O(N log k) where N is total nodes, k is number of lists
- Divide and Conquer: O(N log k)
- Brute Force: O(N log N)
Space Complexity
- Min Heap: O(k) for heap storage
- Divide and Conquer: O(log k) for recursion stack
- Brute Force: O(N) for storing all values