【leetcode】合并 K 个升序链表-25-6

方法：遍历+合并

/*** 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* twoMerge(ListNode* a,ListNode* b){if(!a){return b;}else if(!b){return a;}ListNode* tempa=a->val>=b->val?b:a;ListNode* tempb=a->val>=b->val?a:b;ListNode* aPre=tempa;ListNode* aNext=tempa;while(aNext && tempb){if(aNext->val<=tempb->val){if(aPre==aNext){aNext=aNext->next;}else{aNext=aNext->next;aPre=aPre->next;}}else{aPre->next=tempb;tempb=tempb->next;aPre->next->next=aNext;aPre=aPre->next;}}//aNext one elemif(aPre&& !aNext){aPre->next=tempb;}return tempa;}ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode* res=nullptr;for(int i=0;i<lists.size();i++){if(lists[i]){res=twoMerge(res,lists[i]);}}return res;}
};

方法：分治+合并

/*** 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* twoMerge(ListNode* a,ListNode* b){if(!a){return b;}else if(!b){return a;}ListNode* tempa=a->val>=b->val?b:a;ListNode* tempb=a->val>=b->val?a:b;ListNode* aPre=tempa;ListNode* aNext=tempa;while(aNext && tempb){if(aNext->val<=tempb->val){if(aPre==aNext){aNext=aNext->next;}else{aNext=aNext->next;aPre=aPre->next;}}else{aPre->next=tempb;tempb=tempb->next;aPre->next->next=aNext;aPre=aPre->next;}}//aNext one elemif(aPre&& !aNext){aPre->next=tempb;}return tempa;}ListNode* divideMerge(vector<ListNode*>& lists,int a,int b){if(a==b){return lists[a];}else if(a>b){return nullptr;}int n=(a+b)/2;ListNode* resA=divideMerge(lists,a,n);ListNode* resB=divideMerge(lists,n+1,b);ListNode* res=twoMerge(resA,resB);return res;}ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode* res=nullptr;res=divideMerge(lists,0,lists.size()-1);return res;}
};

方法：结构体排序+优先队列

/*** 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:struct Status{int val;ListNode* ptr;bool operator < (const Status & rhs) const{return rhs.val< val;}};priority_queue <Status> q;ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode* res=new ListNode(-1);// for(auto elem:lists){//     if(elem){//         q.push(elem->val,elem);//     }// }for(int i=0;i<lists.size();i++){if(lists[i]){q.push({lists[i]->val,lists[i]});}}ListNode* finalRes=res;while(!q.empty()){Status temp=q.top();res->next=temp.ptr;q.pop();res=res->next;if(temp.ptr->next){q.push({temp.ptr->next->val,temp.ptr->next});}}res=finalRes;finalRes=finalRes->next;delete res;return finalRes;}
};