Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分治第一道题，这道题还是主要看大家的答案做上来的~

学到的知识点有 c++语法

1.申请内存直接new   ListNode *head = new ListNode(0);

2. 向量vector 转双端队列

          queue<ListNode*> waiting(deque<ListNode*>(lists.begin(), lists.end())); //将vector转为队列

3.合并链表到最后小尾巴这里可以一步解决

       p->next = l1 ? l1 : l2;

        return head->next;

整一个空节点存头，最后返回空节点的下一个就是头

return head->next;

4.队列的神奇用法  pop两次融合成一个再push进去

while (waiting.size() > 1) {

            ListNode *l1 = waiting.front();

            waiting.pop();

            ListNode *l2 = waiting.front();

            waiting.pop();

            waiting.push(merge2(l1, l2));

        } 

放代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0){return NULL;}
        if(lists.size()==1){return lists[0];}
        queue<ListNode*> que(deque(lists.begin(),lists.end()));
        while(que.size()>1){
            ListNode* p1 =que.front();
            que.pop();
            ListNode* p2 =que.front();
            que.pop();
            que.push(mergelink(p1,p2));
        }
        return que.front();
    }
    ListNode* mergelink(ListNode* p1,ListNode*p2){
        ListNode* head = new ListNode(0);
        ListNode* p=head;
        while(p1&&p2){
            if(p1->val>p2->val){
                p->next=p2;
                p=p->next;
                p2=p2->next;
            }else{
                p->next=p1;
                p=p->next;
                p1=p1->next;
            }
        }
        p->next= p1? p1:p2;
        return head->next;
    }
};