1. Problem Statement (Simple Explanation):
You are given an array lists of k sorted linked lists.
Each lists[i] is the head of a singly linked list, sorted in ascending order.
You need to merge all k lists into one sorted linked list.
Return the head of the merged list.
Edge cases:
lists can be empty (k = 0) → return [].
Some lists may be empty (lists[i] == null).
2. Examples:
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
These represent:
List 1: 1 → 4 → 5
List 2: 1 → 3 → 4
List 3: 2 → 6
Merged:
1 → 1 → 2 → 3 → 4 → 4 → 5 → 6
Output: [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
Total number of nodes across all lists <= 104
Each list is sorted in ascending order.
3. Approach 1 – Pairwise Merge (Divide & Conquer, O(N log k), Recommended):
This problem is a k-way merge of sorted lists. A natural strategy:
Repeatedly merge two sorted lists at a time (like LeetCode 21).
Use a divide & conquer strategy to reduce complexity.
Intuition:
This is analogous to merging k sorted arrays:
Merge lists in pairs:
Round 1: merge pairs (0,1), (2,3), (4,5), ...
Round 2: merge resulting lists again in pairs, etc.
Each node participates in O(log k) merge levels.
Let:
N = total number of nodes across all lists.
Time complexity: O(Nlogk)
Space (extra): O(1)
excluding recursion stack if done iteratively, or O(logk) with recursive divide & conquer.
Helper – Merge Two Sorted Lists:
Same as problem 21:
Strategy A – Iterative Merge (Bottom-up):
If lists is empty, return null.
While lists.length > 1:
Create a new list mergedLists.
For every pair of lists (lists[i], lists[i+1]):
Merge them with mergeTwoLists.
Append result to mergedLists.
If odd number of lists, carry the last one forward.
Set lists = mergedLists.
Return lists[0] (the only remaining list).
Pseudo-code (Iterative Pairwise Merge):
Another common method uses a min-heap (priority queue):
Push the head of each non-empty list into a min-heap, keyed by node value.
Repeatedly:
Pop the smallest node from the heap.
Append it to the result list.
If that node has a next, push next into the heap.
Continue until the heap is empty.
Complexity:
Each of the N nodes is pushed & popped once.
Each heap operation is O(log k).
So total time: O(Nlogk), extra space: O(k) for the heap.
Both divide & conquer and heap are good. For simplicity in teaching, the pairwise merge leverages an already-known helper (mergeTwoLists).
5. Java code:
6. C code:
7. C++ code:
8. Python code:
9. JavaScript code:
Comments
Post a Comment