Merge K Sorted List

Merge K Sorted List

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

test

Solution

Merge 2

Actually we could also utilize the merge 2 sorted lists methods and a queue to solve this problem but its worst case is really bad, about O(n^2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
queue<ListNode*> listQueue;
for(const auto& l: lists) if(l) listQueue.push(l);
if(listQueue.empty()) return NULL;
while(listQueue.size() > 1){
ListNode* l1 = listQueue.front();
listQueue.pop();
ListNode* l2 = listQueue.front();
listQueue.pop();
listQueue.push(mergeTwoLists(l1, l2));
}
return listQueue.front();
}
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
if(!l1) return l2;
if(!l2) return l1;
if(l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};

MinHeap

Using a minHeap to ensure the worst time complexity O(nlogk). There are several corner cases that should be handled: NULL in the list, no list at all, add the next of the new head.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct cmpClass{
bool operator() (const ListNode* l, const ListNode* r) const {
return l->val > r->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, cmpClass> minHeap;
for(const auto& l: lists) if(l) minHeap.push(l); //ensure all are valid pointer;
if(minHeap.empty()) return NULL; //before top() to ensure valid pointer;
ListNode *newHead = minHeap.top(), *t = newHead;
minHeap.pop();
if(newHead->next) minHeap.push(newHead->next); //ensure a valid complete minHeap;
while(minHeap.size()){
t->next = minHeap.top();
minHeap.pop();
t = t->next;
if(t->next) minHeap.push(t->next);
}
return newHead;
}
};

Always welcome new ideas and practical tricks, just leave them in the comments!