专业做邯郸网站优化重庆seo入门教程

23. 合并K个排序链表 - 力扣（LeetCode）

抓住链表本身有序这个特点。

我们知道链表排序的主流算法是归并排序，而这题链表本身就有序，自然会联想到归并排序的merge函数：链表排序总结（全）（C++）_qq_32523711的博客-CSDN博客_链表排序 c++

分治

我们可以使用分治的思路进行合并，第一次两两合并，第二次将合并的结果继续两两合并，依次合并下去：

//ListNode *dummy = new ListNode(0);
//auto h = dummy;
ListNode dummy, *h = &dummy;

class Solution {
public:ListNode* mergeTwo(ListNode* left, ListNode* right){if(!left || !right) return left ? left : right;ListNode dummy, *h = &dummy;while(left && right){if(left->val < right->val){h->next = left;left = left->next;}else{h->next = right;right = right->next;}h = h->next;}h->next = left ? left : right;return dummy.next;}ListNode* merge(vector<ListNode*>& lists, int low, int high){if(low == high)  return lists[low];auto mid = (low+high)>>1;ListNode *left = merge(lists, low, mid);ListNode *right = merge(lists, mid+1, high);return mergeTwo(left, right);}ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.size() == 0)   return NULL;return merge(lists, 0, lists.size() - 1);}
};

之前也说过，归并排序还可以用迭代的思路来写：

class Solution {
public:ListNode* mergeTwo(ListNode* left, ListNode* right){ListNode dummy, *h = &dummy;while(left && right){if(left->val < right->val){h->next = left;left = left->next;}else{h->next = right;right = right->next;}h = h->next;}h->next = left ? left : right;return dummy.next;}ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.size() == 0)   return NULL;for(int i = 1; i < lists.size(); i += i){//即便size为奇数也无所谓，因为前面的一直合并下去总会合并为一个//将剩余的那个与合并的一大个再合并就行//或者在vector末尾加一个空链表让其size变成偶数也行for(int j = 0; j+i < lists.size(); j += 2*i){lists[j] = mergeTwo(lists[j], lists[j+i]);lists[j+i] = NULL;//已经合并到上面去了，所以这一部分可以置空}}return lists[0];}
};

merge函数可以直接使用引用传递：

class Solution {
public:void mergeTwo(ListNode* &left, ListNode* &right){ListNode dummy, *h = &dummy;while(left && right){if(left->val < right->val){h->next = left;left = left->next;}else{h->next = right;right = right->next;}h = h->next;}h->next = left ? left : right;left = dummy.next; //合并完之后放回left的位置，即vector中的原位置}ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.size() == 0)   return NULL;for(int i = 1; i < lists.size(); i += i){for(int j = 0; j+i < lists.size(); j += 2*i)mergeTwo(lists[j], lists[j+i]);}return lists[0];}
};

堆

可以看这个的图：
C++ 优先队列&两两合并&分治合并（图解） - 合并K个排序链表 - 力扣（LeetCode）

使用小顶堆来排序，注意比较符号需要自己定义，k路归并：

class Solution {
public:struct cmp{  bool operator() (ListNode *a,ListNode *b){return a->val > b->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, cmp> q;for(auto p : lists){if(p)   q.push(p); //空链表就不放进去} ListNode dummy, *h = &dummy;while(!q.empty()){auto cur = q.top();q.pop();if(cur->next)   q.push(cur->next);h->next = cur;h = cur;}return dummy.next;}
};