题解 | #牛群的合并# 多路归并

知识点

多路归并 / 优先队列（堆）

思路解析

链表形式的多路归并题，由于原来的k个序列每一个都是递增的，只需要先把k个序列的头结点加入小顶堆，依次抛出堆顶元素后把堆顶元素的非空的next结点加入堆。即可实现多路归并得到有序序列。

时间复杂度

堆的每次插入的时间复杂度是

添加n个元素的总时间复杂度是

n是全部链表的总结点数

AC code (C++)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 多路归并
        auto cmp = [](ListNode* p1, ListNode* p2) {
            return p1->val > p2->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q(cmp);
        for (auto p : lists) {
            if (p) q.push(p);
        }
        auto dummy = new ListNode(-1);
        auto cur = dummy;
        while (q.size()) {
            auto t = q.top();
            q.pop();
            cur->next = t;
            cur = cur->next;
            if (t->next) q.push(t->next);
        }
        cur->next = nullptr;
        return dummy->next;
    }
};