题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

样例

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

算法1

(分治) $O(mlogn)$

分而治之，两两归并，最后归并成一条。
例如：1、2、3、4一共四条链表，1与2归并成1+2，3与4归并成3+4， 1+2与3+4再归并成1+2+3+4。

时间复杂度

m为链表总长度，n为链表数量，一共归并$O(logn)$次，每一次时间复杂度是$O(m)$，所以总复杂度是$O(mlogn)$

参考文献

C++ 代码

/**
 * 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.empty()) return nullptr;
        int step = 1, n = lists.size();
        while (step < n){
            for (int i = 0; i + step < n; i += 2 * step){
                lists[i] = merge2Lists(lists[i], lists[i + step]);
            }
            step <<= 1;
        }
        return lists[0];
    }

    ListNode * merge2Lists(ListNode *l1, ListNode *l2){
        if (!l1) return l2;
        if (!l2) return l1;
        ListNode *dummy = new ListNode(0), *p = dummy;
        while (l1 && l2){
            if (l1->val <= l2->val) p->next = l1, l1 = l1->next;
            else p->next = l2, l2 = l2->next;
            p = p->next;
        }

        if (l1) p->next = l1;
        if (l2) p->next = l2;

        p = dummy->next;
        delete dummy; dummy = nullptr;
        return p;
    }
};

算法2

(堆) $O(mlogn)$

将n条链表头节点放入堆，根据节点值的大小排序，每次取出堆顶节点，也是最小节点加到答案尾部，然后将该节点的后续节点放入堆种，循环往复完成归并。

时间复杂度

m为链表总长度，n为链表数量，一共要从堆中取出$O(m)$次，从堆中取元素的复杂度是$O(logn)$次，所以总复杂度是$O(mlogn)$

参考文献

C++ 代码

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

struct cmp{
    bool operator() (ListNode *p1, ListNode *p2) const{ // 这里重载的运算符是(),可不是<或者>
        return p1->val > p2->val; // 小根堆，所以返回 > 
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        priority_queue<ListNode *, vector<ListNode *>, cmp> pq;
        for (ListNode *head: lists) 
            if (head) pq.push(head);

        ListNode *dummy = new ListNode(0), *p = dummy;
        while (pq.size()){
            ListNode *node = pq.top(); pq.pop();
            p->next = node;
            p = p->next;
            if (node->next) pq.push(node->next);
        }

        p = dummy->next;
        delete dummy; dummy = nullptr;
        return p;
    }
};