LeetCode 23. Merge k Sorted Lists
经典题
解法一：优先队列
class CMP{
public:
bool operator () (const ListNode* a, const ListNode * b) const {
return a->val > b->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode *head = nullptr;
if (lists.size() == 0){
return head;
}
ListNode *tail = nullptr;
priority_queue<ListNode*, vector<ListNode*>, CMP> que;
for (int i = 0; i < lists.size(); ++i){
if (lists[i] != nullptr){
que.push(lists[i]);
}
}
if (que.empty()){
return head;
}
head = que.top();
tail = head;
que.pop();
if (tail->next != nullptr){
que.push(tail->next);
}
while (!que.empty()){
ListNode *curNode = que.top();
que.pop();
tail->next = curNode;
tail = tail->next;
if (tail->next != nullptr){
que.push(tail->next);
}
}
return head;
}
};
解法二：基于分治的思想，每次找两个链表合并成一个，一直到只剩最后一个，这里用一个queue提高效率，vector里erase是很耗时的
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode *head = nullptr;
if (lists.size() == 0){
return head;
}
queue<ListNode *> que;
for (int i = 0; i < lists.size(); ++i){
que.push(lists[i]);
}
while (que.size() > 1){
ListNode *a = que.front();
que.pop();
ListNode *b = que.front();
que.pop();
ListNode *c = mergeList(a, b);
que.push(c);
}
return que.front();
}
ListNode *mergeList(ListNode *a, ListNode *b){
if (a == nullptr){
return b;
}
if (b == nullptr){
return a;
}
ListNode *head = nullptr, *tail = nullptr;
if (a->val < b->val){
head = a;
a = a->next;
}else{
head = b;
b = b->next;
}
tail = head;
while (a != nullptr && b != nullptr){
if (a->val < b->val){
tail->next = a;
a = a->next;
}else{
tail->next = b;
b = b->next;
}
tail = tail->next;
}
if (a != nullptr){
tail->next = a;
}
if (b != nullptr){
tail->next = b;
}
return head;
}
};
0 个回复