Topic 23 Merge K ascending linked lists
9.1 official analysis
(when I first did this problem, I first thought of merging the two linked lists in order, but what I wrote was always overtime. Compared with the sequential merging in the solution, it was too complicated and there were many useless steps.)
The following will use several different methods to achieve the merge list.
Solution 1: sequential merging
Solution 2: divide and conquer (two by two)
Solution 3: use priority queue merging
Before looking at the following solutions, let's look at how to merge two ordered linked lists?
Assuming that the length of linked lists a and b is n, the merging should be completed at the time cost of O(n) and the space cost of O(1). Our goal is to [adjust the next pointer of linked list elements in place to complete the merge].
- First of all, you need a variable head to save the head of the merged linked list. You can set the head as a virtual head (convenient for code writing). After the whole linked list is merged, you can return to its next position.
- We need a constantly changing pointer tail to record the previous position of the next insertion position, and two pointers aPtr and bPtr to record the first bit of the unconsolidated part of a and b.
- When aPtr and bPtr are not empty, the merge with smaller val is taken; If aPtr is empty, the whole bPtr and subsequent elements are merged; The same goes for aPtr.
- When merging, first adjust the next attribute of the tail, and then move the tail and Ptr later.
/*
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
// Merge two ordered linked lists
ListNode* merge_two_lists(ListNode* a, ListNode* b) {
if (!a || !b) {
return a ? a : b;
}
ListNode head;
ListNode* tail = &head;
ListNode* aPtr = a;
ListNode* bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr;
aPtr = aPtr->next;
}
else {
tail->next = bPtr;
bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = (aPtr ? aPtr : bPtr);
return head.next;
}
Complexity analysis
- Time complexity: O(n).
- Space complexity: O(1).
9.2 solution 1
Here is the simplest solution that can be thought of first: sequential merging.
class Solution {
public:
// Merge two ordered linked lists
ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
if ((!a) || (!b)) return a ? a : b;
ListNode head;
ListNode* tail = &head;
ListNode* aPtr = a;
ListNode* bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr;
aPtr = aPtr->next;
} else {
tail->next = bPtr;
bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = (aPtr ? aPtr : bPtr);
return head.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) {
return nullptr;
}
ListNode* result = nullptr;
for (size_t i = 0; i < lists.size(); ++i) {
result = mergeTwoLists(result, lists[i]);
}
return result;
}
};
The memory consumption of this solution is not high, but the execution time is very high!
Execution time: 170 ms,
Memory consumption: 12.7 MB
Complexity analysis
Time complexity: O(k) ² n).
Space complexity: O(1).
9.3 solution 2
The method of divide and conquer is similar to the combination of two in merge sort( Recursion!)
class Solution {
public:
// Merge two ordered linked lists
ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
if ((!a) || (!b)) return a ? a : b;
ListNode head;
ListNode* tail = &head;
ListNode* aPtr = a;
ListNode* bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr;
aPtr = aPtr->next;
} else {
tail->next = bPtr;
bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = (aPtr ? aPtr : bPtr);
return head.next;
}
// Recursive operation
ListNode* merge(vector<ListNode*>& lists, int low, int high) {
if (low == high) return lists[low];
if (low > high) return nullptr;
// In fact, it can also be mid = low + (high - low) / 2; But the following is faster!
int mid = (low + high) >> 1;
return mergeTwoLists(merge(lists, low, mid), merge(lists, mid + 1, high));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 1);
}
};
Execution time: 24 ms,
Memory consumption: 12.7 MB
9.4 solution 3
The idea of using priority queue merging is different from the previous two methods, that is, all the linked lists are stored in a priority queue, and the smallest node in the front of the elements that are not merged in each linked list is extracted each time (in fact, the first element of the queue is extracted, and once extracted, the queue is removed), until all the linked lists are extracted.
Because Comp function compares the largest heap and maintains the increasing relationship by default, if we want to get the minimum node value, the comparison function should maintain the decreasing relationship, so the greater than sign is returned in operator() instead of the less than sign for comparison.
class Solution {
struct Comp {
bool operator() (ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) {
return nullptr;
}
priority_queue<ListNode*, vector<ListNode*>, Comp> q;
for (ListNode* list : lists) {
if (list) {
q.push(list);
}
}
// You can also use listnode result; ListNode* cur = &result; Finally, return result.next;
ListNode* result = new ListNode(0);
ListNode* cur = result;
while (!q.empty()) {
cur->next = q.top();
q.pop();
cur = cur->next;
if (cur->next) {
q.push(cur->next);
}
}
return result->next;
}
};