0023.Merge k Sorted Lists.md

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 = [[]]
输出：[]

code

暴力法：将列表中所有元素存到数组里，再sort。假设k个列表的平均长度为n，时间复杂度：$(kn)^2$

/**
 * 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) {
        int size = lists.size(), i;
        ListNode *tmp;
        vector<int> vt;
        for(i=0; i<size; i++){
            tmp = lists[i];
            while(tmp){
                vt.push_back(tmp->val);
                tmp = tmp->next;
            }
        }
        sort(vt.begin(), vt.end());
        ListNode* t1 = new ListNode(0);
        tmp = t1;
        for(i=0, size=vt.size(); i<size; i++){
            ListNode* t2 = new ListNode(vt[i]);
            t1->next = t2;
            t1 = t2;
        }
        return tmp->next;
    }
    bool cmp(const int &a, const int &b){
        return a < b;
    }
};

分治法：k个列表两两组合，排序后再两两组合，以此类推。时间复杂度：$knlogk$

/**
 * 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) {
        int size = lists.size();
        if(size == 0) return NULL;
        return mergeK(lists, 0, size-1);
    }
    ListNode* mergeK(vector<ListNode*>& lists, int left, int right){
        if(left == right) return lists[left];
        if(left + 1 == right) return mergeTwo(lists[left], lists[right]);
        ListNode* l1 = mergeK(lists, left, (left + right)>>1);
        ListNode* l2 = mergeK(lists, ((left + right)>>1)+1, right);
        return mergeTwo(l1, l2);
    }
    ListNode* mergeTwo(ListNode* l1, ListNode* l2){
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val < l2->val){
            l1->next = mergeTwo(l1->next, l2);
            return l1;
        }
        else{
            l2->next = mergeTwo(l2->next, l1);
            return l2;
        }
    }
};

堆排序法：维护一个大小为k的堆，将k个列表的第一个元素插入堆，每次从堆中取出一个结点后，将该结点的next结点加入堆。时间复杂度：$knlogk$

class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};