23. Merge k Sorted Lists
1. 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.
2. Example
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: []
3. Constraints
- k == lists.length
- 0 <= k <= 10$^4$
- 0 <= lists[i].length <= 500
- -10$^4$ <= lists[i][j] <= 10$^4$
- lists[i] is sorted in ascending order.
- The sum of lists[i].length will not exceed 10$^4$.
4. Solutions
Divide and Conquer
k = lists.size(), n = lists.front().size()
Time complexity: O(knlogk)
Space complexity: O(logk)
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
return merge_lists(lists, 0, lists.size() - 1);
}
private:
ListNode *merge_two_lists(ListNode *l1, ListNode *l2) {
ListNode dummy;
auto iter = &dummy;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val <= l2->val) {
iter->next = l1;
l1 = l1->next;
} else {
iter->next = l2;
l2 = l2->next;
}
iter = iter->next;
}
iter->next = l1 == nullptr ? l2 : l1;
return dummy.next;
}
ListNode *merge_lists(vector<ListNode *> &lists, int left, int right) {
if (left > right) {
return nullptr;
}
if (left == right) {
return lists[left];
}
int middle = left + (right - left) / 2;
return merge_two_lists(
merge_lists(lists, left, middle), merge_lists(lists, middle + 1, right));
}
};