题目链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/
题目如下：
解1、两两合并
/**
* Definition for singly-linked list.
* 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) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* res=nullptr;
if(lists.size()==0) return res;
if(lists.size()==1) return lists[0];
for(int i=0;i<lists.size();i++){
res=mergetwoKLists(res,lists[i]);
}
return res;
}
ListNode* mergetwoKLists(ListNode* l1,ListNode* l2){
if(!l1) return l2;
if(!l2) return l1;
ListNode* dummy=new ListNode(-1),*tail=dummy;
while(l1&&l2){
if(l1->val<l2->val){
tail->next=l1;
l1=l1->next;
}else {
tail->next=l2;
l2=l2->next;
}
tail=tail->next;
}
if(l1) tail->next=l1;
else if(l2) tail->next=l2;
return dummy->next;
}
};
解2、归并合并
/**
* Definition for singly-linked list.
* 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) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists,0,lists.size()-1);
}
ListNode* merge(vector<ListNode*>& lists,int l,int r){
if(l==r) return lists[l];
if(l>r) return nullptr;
int mid=l+(r-l)/2;//(l+r)>>1;可以，不能l+(r-l)>>1，右移还是不太懂她
return mergetwoKLists(merge(lists,l,mid),merge(lists,mid+1,r));
}
ListNode* mergetwoKLists(ListNode* l1,ListNode* l2){
if(!l1) return l2;
if(!l2) return l1;
ListNode* dummy=new ListNode(-1),*tail=dummy;
while(l1&&l2){
if(l1->val<l2->val){
tail->next=l1;
l1=l1->next;
}else {
tail->next=l2;
l2=l2->next;
}
tail=tail->next;
}
if(l1) tail->next=l1;
else if(l2) tail->next=l2;
return dummy->next;
}
};
解3、小顶堆
/**
* Definition for singly-linked list.
* 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) {}
* };
*/
class Solution {
public:
//小顶堆做法
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size()==0) return nullptr;
priority_queue<ListNode*,vector<ListNode*>,Cmp> minheap;
for(auto e:lists){
if(e) minheap.push(e);
}
auto dummy=new ListNode(-1);
auto tail=dummy;
while(!minheap.empty()){
auto top=minheap.top();
minheap.pop();
tail->next=top;
tail=tail->next;
if(top->next) minheap.push(top->next);
}
return dummy->next;
}
private:
struct Cmp{
bool operator()(ListNode* l1,ListNode* l2){
return l1->val > l2->val; //目的：优先出列判定为!cmp，所以反向定义实现最小值优先
}
};
};
