L23 合并K个有序链表

链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

解1：分治法，对半划分，如果有6个链表，合并0，3；1，4；2，5（n+1）/2;
解2：最小堆

//最小堆
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp=[](ListNode * &a, ListNode*&b){
            return a->val > b->val;
        };
        priority_queue<ListNode*,vector<ListNode*>,decltype(cmp) > q(cmp);
        for(auto node:lists){
            if(node) q.push(node);
        }
        ListNode *dummy = new ListNode(-1),*cur=dummy;
        while(!q.empty()){
            auto t = q.top();
            q.pop();
            cur->next = t;
            cur = cur->next;
            if(cur->next) q.push(cur->next);
        }
        return dummy->next;
    }

ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<int> nums;
        if (lists.size()==0) return NULL;
        if (lists.size()==1) return lists[0];
        ListNode *cur = lists[0];
        for(int i=0;i<lists.size();i++){
            // head
            cur = lists[i];
            // give all num
            while(cur!=NULL){
                nums.push_back(cur->val);
                cur = cur->next;
            }
        }
        cout << nums.size() << endl;
        if(nums.empty()) return NULL;
        sort(nums.begin(),nums.end());
        ListNode *newhead = new ListNode(nums[0]);
        cur = newhead;
        for(int i=1;i<nums.size();i++){
            cur->next = new ListNode(nums[i]);
            cur = cur->next;     
        }
        cur->next =NULL;
        return newhead;
    }