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 linked 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.
Solve it on LeetCode
Approaches
1. Naive Approach: Brute Force Merging
Intuition:
The simplest strategy is to flatten the k linked lists into a single list, sort it, and then reconstruct the linked list from this sorted data. This approach is easy to implement but not efficient.
Steps:
- Traverse each linked list and store each node’s value in a list.
- Sort this list.
- Use the sorted values to construct a new linked list.
Code:
- Time Complexity: O(N log N), where N is the total number of nodes across all k lists. We gather all values, and then sort them.
- Space Complexity: O(N), to store all node values.
2. Heap Approach: Using a Min-Heap
Intuition:
Utilize a min-heap to efficiently retrieve the smallest current head from k lists and build the final output list. PriorityQueue in Java can manage this as a min-heap by default.
Steps:
- Insert the head of each list into a min-heap.
- Continuously extract the smallest element from the heap, add it to the output list, and insert its next element back into the heap.
Code:
- Time Complexity: O(N log k), where N is the total number of nodes and k is the number of linked lists. Each node insertion/extraction in the heap takes log k time.
- Space Complexity: O(k), for storing k nodes in the heap.
3. Optimized Approach: Divide and Conquer
Intuition:
Use the divide-and-conquer technique. Merge lists in pairs and repeat the process until one list remains.
Steps:
- Pair lists and merge each pair.
- Repeat the pairing and merging until only one list remains.
Code:
- Time Complexity: O(N log k), as each merge operation deals with N nodes in log k depth of recursive calls.
- Space Complexity: O(log k), due to the recursion stack.