题目:
Merge k sorted linked lists and return it as one sorted list.
Analyze and describe its complexity.
Example
Given lists:
[
2->4->null,
null,
-1->null
],
return -1->2->4->null
.
题解:
Solution 1 ()
class Solution {
public:
struct compare {
bool operator() (const ListNode* a, const ListNode* b) {
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode*, vector<ListNode*>, compare> q;
for (auto l : lists) {
if (l) {
q.push(l);
}
}
ListNode* head = nullptr, *pre = nullptr, *tmp = nullptr;
while (!q.empty()) {
tmp = q.top();
q.pop();
if(!pre) {
head = tmp;
} else {
pre->next = tmp;
}
pre = tmp;
if (tmp->next) {
q.push(tmp->next);
}
} return head;
}
};
Solution 2 ()
class Solution {
public:
ListNode* mergeKLists(vector<ListNode *> &lists) {
if (lists.empty()) {
return nullptr;
}
int n = lists.size();
while (n > ) {
int k = (n + ) / ;
for (int i = ; i < n / ; ++i) {
lists[i] = mergeTwoLists(lists[i], lists[i + k]);
}
n = k;
}
return lists[];
} ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(-);
ListNode* cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1) {
cur->next = l1;
} else {
cur->next = l2;
} return dummy->next;
}
};
Solution 3 ()
class Solution {
public:
static bool heapComp(ListNode* a, ListNode* b) {
return a->val > b->val;
}
ListNode* mergeKLists(vector<ListNode*>& lists) { //make_heap
ListNode head();
ListNode *curNode = &head;
vector<ListNode*> v;
for(int i =; i<lists.size(); i++){
if(lists[i]) v.push_back(lists[i]);
}
make_heap(v.begin(), v.end(), heapComp); //vector -> heap data strcture while(v.size()>){
curNode->next=v.front();
pop_heap(v.begin(), v.end(), heapComp);
v.pop_back();
curNode = curNode->next;
if(curNode->next) {
v.push_back(curNode->next);
push_heap(v.begin(), v.end(), heapComp);
}
}
return head.next;
}
};