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

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

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

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

Solution

参考 LeetCode官方

• 顺序合并
• 借助两个链表合并的思想
• 时间复杂度 O(k^2^ n)，空间复杂度 O(1)

// @lc code=start
/**
 * 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:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0)
            return nullptr;
        
        ListNode* ans = nullptr;
        for(int i=0; i<lists.size(); ++i){
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;        
    }
private:
    ListNode* mergeTwoLists(ListNode* a, ListNode* b){
        if(!a || !b) return a ? a: b;
        ListNode* dummyHead = new ListNode(-1);
        ListNode* cur = dummyHead, *aPtr=a, *bPtr=b;
        while(aPtr && bPtr){
            if(aPtr->val < bPtr->val){
                cur->next = aPtr;
                aPtr = aPtr->next;
            } else {
                cur->next = bPtr;
                bPtr = bPtr->next;
            }
            cur = cur->next;
        }
        cur->next = (aPtr ? aPtr : bPtr);
        return dummyHead->next;
    }
};
// @lc code=end

• 分治合并
• 时间复杂度 O(kn * log k)，空间复杂度 O(log k)

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size()-1);        
    }
private:
    ListNode* merge(vector<ListNode*>& lists, int l, int r){
        if(l==r)
            return lists[l];
        if(l>r)
            return nullptr;
        int mid = (l+r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid+1, r));
    }

    ListNode* mergeTwoLists(ListNode* a, ListNode* b){
        if(!a || !b) return a ? a: b;
        ListNode* dummyHead = new ListNode(-1);
        ListNode* cur = dummyHead, *aPtr=a, *bPtr=b;
        while(aPtr && bPtr){
            if(aPtr->val < bPtr->val){
                cur->next = aPtr;
                aPtr = aPtr->next;
            } else {
                cur->next = bPtr;
                bPtr = bPtr->next;
            }
            cur = cur->next;
        }
        cur->next = (aPtr ? aPtr : bPtr);
        return dummyHead->next;
    }
};

• 利用优先队列
• 维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。
• 时间复杂度 O(kn * log k)，空间复杂度 O(k)

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

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for(auto node: lists){
            if(node)
                pq.push({node->val, node});
        }
        ListNode* dummyHead = new ListNode(-1), *cur = dummyHead;
        while(!pq.empty()){
            auto S = pq.top();
            pq.pop();
            cur->next = S.ptr;
            cur = cur->next;
            if(S.ptr->next)
                pq.push({S.ptr->next->val, S.ptr->next});
        }
        return dummyHead->next;
    }
};