LeetCode 23.合并k个升序链表

题目：

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例2： 

输入：lists = []

输出：[]

示例3：

 输入：lists = [[]]

 输出：[]

/**
 * 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) {}
 * };
 */

看到这个题首相想到的就是暴力转化破解，思路就是把链表的所有结点值放进一个数组里面，对这个数组排序，我们可以用vector动态创建，完事之后，对数组进行从小到大的默认排序，最后遍历整个数组根据值去创建一个一个新的结点，把这些结点串在一起返回就行

代码如下：

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0)return 0;
        ListNode* dummy=new ListNode(-1);
        ListNode*p=dummy;
        vector<int>vv;//把所有链表的值放进vector里面
        for(int i=0;i<lists.size();++i)
        {          
            while(lists[i]!=nullptr)
            {
                 vv.push_back(lists[i]->val); 
                 lists[i]=lists[i]->next;
            }   
        }
        sort(vv.begin(),vv.end());
        for(int i=0;i<vv.size();++i)
        {
            ListNode* newNode=new ListNode(vv[i]);//以数组每个数创造一个结点
            p->next=newNode;
            p=p->next;
        }
        return dummy->next;
    }
};

不过这么写的话时间复杂度高的一批，空间上还得创建维护k个结点大小的动态数组。

不过怎么说呢刚开始刷算法，能写出来就挺好的了，反正我当初这么写出来也挺激动的，分分钟搞定一个hard题，不过学了优先级队列，就可以对这个题的解法进行优化

都知道优先级队列底层是拿堆实现的，默认的大顶堆，每次把元素放进优先队列里，他会自动给你排序，对头就是优先级最高的那个，这里的优先级可能是大小可能是什么的，对于自定义的类型我们可以自定义他的排序方式

总之这道题他要从小到大排，我们就可以先把k个链表的各个头放进去，以小顶堆的方式去创建优先队列，当然这个排序顺序需要我们自己写，因为不是内置类型，然后每次取出的话就是最小的，取出一个在放进去一个，队列就会自己排序，再取再放就行

整体思路就是：

    1. 新建哨兵节点, 指向合并后的链表; 新建一个优先级队列priority_queue
    2. 将所有的链表的第一个元素如队列
    3. 将队列的第一元素出队列, 插入到新链表的尾部
    4. 将第一元素的下一个元素入队(比较剩下的链表的第1个元素和第i个链表的第2个元素)
    5. 重复3-4步, 得到新的队列.

优先队列 q中的元素个数最多是 k，所以一次 取出或者 插入 方法的时间复杂度是 O(logk)；所有的链表节点都会被加入和弹出 q，所以算法整体的时间复杂度是 O(Nlogk)，其中 k 是链表的条数，N 是这些链表的节点总数。

实现代码：

class Solution {
public:
    bool operator()(ListNode* a,ListNode* b)const
    {
        return a->val>b->val;
    }
 
    ListNode* mergeKLists(vector<ListNode*>& lists) {
    if(lists.size()==0)return nullptr;
     priority_queue<ListNode*, vector<ListNode*>, Solution> q;
     ListNode* dummy=new ListNode(-1);
     for(auto x:lists)
     {
         if(x!=nullptr)
         {
              q.push(x);
         }
     }
    ListNode* p=dummy;
    while(!q.empty())
    {
        ListNode* tmp=q.top();
        q.pop();
        if(tmp->next!=nullptr)
        {
            q.push(tmp->next);
        }
        p->next=tmp;
        p=p->next;
    }
    return dummy->next;
 
 
    }
};

对于那里面的自定义函数可能有的人看着怪怪的，明明是大于怎么排出来就是小于呢。

主要还是优先队列底层堆其实是个完全二叉树

这和源码的实现有关系. 根据源码实现这里比较的是当前节点和孩子节点， 也就是当前节点大于孩子节点的时候才向下调整，因此得到的是最小堆。内置类型的greater<>这个改成小顶堆也是这样.所以没毛病，在这大于对应的其实是小顶堆，排出来是从小到大

借着这道题呢也把优先队列好好复习一下，刷题的时候有时候会用到，比如问你前k个高频元素之类的题，之前做过。粘一些链接以后复习的时候也能看

 priority_queue 中存放pair时，自定义排序的写法_ccczxacxzxcz的博客-CSDN博客

力扣347. 前 K 个高频元素与C++stl优先队列(大小根堆)的自定义排序用法总结_weixin_43739821的博客-CSDN博客 C++中优先队列priority_queue的基础用法_AlbertS的博客-CSDN博客_优先队列怎么写

 一文讲明白优先级队列为啥按less排序却是从大到小_技术交流_牛客网 (nowcoder.com)

做过这个题的肯定就做过合并2个升序链表，这个是k个其实还可以把之前写的合并两个的封装成一个merge函数，放在这个题里面就是不断调用，两两合并。也能做出来

做点小优化呢就是这个思路上利用分治的思想取优化一下，不过我没具体了解。

个人认为掌握暴力和优先队列，学会优先队列是做完这个题要掌握的，当然分治思想也在这个题里要学学，哎写完这句话我就去看看这个题的分治！

多种写法

/**
 * 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:
    bool operator()(ListNode *a,ListNode*b)const
    {
        return a->val>b->val;
    }
    static bool cmp(ListNode *a,ListNode*b)
    {
         return a->val>b->val;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0)return nullptr;
        //priority_queue<ListNode*,vector<ListNode*>,Solution> que;
        //priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)*> que(cmp);
        priority_queue<ListNode*,vector<ListNode*>,decltype(&cmp)> que(cmp);
       auto cmp1=[](ListNode *a,ListNode*b)
    {
         return a->val>b->val;
    };
   // priority_queue<ListNode*,vector<ListNode*>,decltype(cmp1)> que(cmp1); 
    //function<bool(ListNode *a,ListNode*b)>fun(cmp);
    //priority_queue<ListNode*,vector<ListNode*>,decltype(fun)> que(fun); 
   // function<bool(ListNode *a,ListNode*b)>fun(cmp1);
   // priority_queue<ListNode*,vector<ListNode*>,decltype(fun)> que(fun);
       
        ListNode *dummy=new ListNode(-1);
        ListNode *cur=dummy;
        for(auto x:lists)
        {
            if(x!=nullptr)
            {
                 que.push(x);
            }
        }
        while(!que.empty())
        {
            ListNode *tmp=que.top();
            que.pop();
            if(tmp->next)
            {
                que.push(tmp->next);
            }
            cur->next=tmp;
            cur=cur->next;
 
        }
        return dummy->next;
 
 
 
 
 
    }
};