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 is the number of nodes in all lists
Time complexity: O(nlogk)
Space complexity: O(logk)
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
return merge_lists(lists, 0, lists.size());
}
private:
ListNode *merge_two_lists(ListNode *l1, ListNode *l2) {
ListNode dummy;
ListNode *tail = &dummy;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->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 + 1 == right) {
return lists[left];
}
int middle = left + (right - left) / 2;
return merge_two_lists(merge_lists(lists, left, middle), merge_lists(lists, middle, right));
}
};
Priority Queue
k = lists.size(), n is the number of nodes in all lists
Time complexity: O(nlogk)
Space complexity: O(k)
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
ListNode dummy;
ListNode *tail = &dummy;
auto compare_node = [](ListNode *a, ListNode *b) { return a->val > b->val; };
priority_queue<ListNode *, vector<ListNode *>, decltype(compare_node)> least_nodes;
for (ListNode *l : lists) {
if (l != nullptr) {
least_nodes.push(l);
}
}
while (!least_nodes.empty()) {
ListNode *node = least_nodes.top();
least_nodes.pop();
tail->next = node;
tail = tail->next;
if (node->next != nullptr) {
least_nodes.push(node->next);
}
}
return dummy.next;
}
};