【C++】LeetCode：LCR 078. 合并 K 个升序链表-EW帮帮网

题干：

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

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

解法：优先队列

/**
 * 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) {}
 * };
 */
 auto cmp = [](ListNode*a,ListNode*b){
    return a->val>b->val;
};
class Solution {
public:
         ListNode * mergeTwoLists(ListNode * a,ListNode * b){
            ListNode * dummy = new ListNode(0);
            ListNode * cur = dummy;
            while (a!= nullptr&&b!= nullptr){
                if (a->val<b->val){
                    cur->next = a;
                    a = a->next;
                } else{
                    cur->next = b;
                    b = b->next;
                }
                cur = cur->next;
            }
            cur->next = (a== nullptr)?b:a;
            return dummy->next;
        };

        ListNode *mergeKLists(std::vector<ListNode*>& lists){

            std::priority_queue<ListNode*,std::vector<ListNode*>, decltype(cmp)> minHeap(cmp);

            for (auto list:lists) {
                if(list!= nullptr){
                    minHeap.push(list);
                }
            }

            ListNode dummy = ListNode(0);
            ListNode * tail = &dummy;

            while (!minHeap.empty()){
                ListNode * miniNode = minHeap.top();
                minHeap.pop();

                tail->next = miniNode;
                tail = tail->next;

                if (miniNode->next!= nullptr){
                    minHeap.push(miniNode->next);
                }
            }
            return  dummy.next;
        };
};

举例分步解析：

示例：合并三个升序链表

假设我们有三个升序链表：

链表 1：1 -> 4 -> 5
链表 2：1 -> 3 -> 4
链表 3：2 -> 6

初始化状态：

最小堆的基本概念

最小堆 是一种特殊的二叉树结构，其中每个节点的值都小于或等于其子节点的值。
堆顶（即根节点）是整个堆中最小的元素。
最小堆通常用于实现优先队列，因为它可以在 O(log n) 时间内插入和删除元素，并且可以在 O(1) 时间内访问最小元素。

我们的目标是将这三个链表合并成一个升序链表。为了实现这一点，我们可以使用最小堆来高效地找到当前所有链表中值最小的节点。

初始状态

在开始时，我们将每个链表的头节点加入最小堆。此时，最小堆的状态如下：

堆顶是 1，它来自链表 1 或链表 2（因为我们有两个 1）。
堆的其他节点分别是链表 2 的头节点 1 和链表 3 的头节点 2。

第一步：取出堆顶元素

我们从堆中取出最小的元素 1（来自链表 1），并将其加入结果链表。然后，我们将链表 1 的下一个节点 4 加入堆中。此时，堆的状态变为：

堆顶现在是 1，它来自链表 2。
堆的其他节点分别是链表 1 的下一个节点 4 和链表 3 的头节点 2。

第二步：再次取出堆顶元素

我们从堆中取出最小的元素 1（来自链表 2），并将其加入结果链表。然后，我们将链表 2 的下一个节点 3 加入堆中。此时，堆的状态变为：

堆顶现在是 2，它来自链表 3。
堆的其他节点分别是链表 1 的下一个节点 4 和链表 2 的下一个节点 3。

第三步：继续取出堆顶元素

我们从堆中取出最小的元素 2（来自链表 3），并将其加入结果链表。然后，我们将链表 3 的下一个节点 6 加入堆中。此时，堆的状态变为：

堆顶现在是 3，它来自链表 2。
堆的其他节点分别是链表 1 的下一个节点 4 和链表 3 的下一个节点 6。

第四步：继续取出堆顶元素

我们从堆中取出最小的元素 3（来自链表 2），并将其加入结果链表。然后，我们将链表 2 的下一个节点 4 加入堆中。此时，堆的状态变为：

堆顶现在是 4，它来自链表 1。
堆的其他节点分别是链表 2 的下一个节点 4 和链表 3 的下一个节点 6。

第五步：继续取出堆顶元素

我们从堆中取出最小的元素 4（来自链表 1），并将其加入结果链表。堆的状态变为：

堆顶现在是 4，它来自链表 2。
堆的其他节点是链表1的下一节点5，链表 3 的下一个节点 6。

第六步：继续取出堆顶元素

我们从堆中取出最小的元素 4（来自链表 2），并将其加入结果链表。此时，链表 2 已经遍历完毕，没有更多的节点可以加入堆中。

堆的状态变为：堆顶现在是 5，它来自链表 1，其他节点是6来自链表3。

第七步：继续取出堆顶元素

我们从堆中取出元素 5，并将其加入结果链表。

第八步：继续取出堆顶元素

我们从堆中取出元素 6，并将其加入结果链表。

最终结果

合并后的链表为：1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

时间复杂度分析

初始化最小堆

操作：将 k 个链表的头节点插入最小堆。
复杂度：每次插入操作的时间复杂度是 O(log⁡k)，因此初始化堆的时间复杂度为 O(klog⁡k)。

提取最小元素和插入新元素

操作：每次从堆中提取最小元素并插入新的节点。
复杂度：每次提取最小元素和插入新元素的操作时间复杂度均为 O(log⁡k)。
次数：总共需要进行 N 次提取和插入操作（因为总共有 N 个节点）。
总复杂度：O(Nlog⁡k)

总时间复杂度

初始化堆：O(klog⁡k)
提取和插入操作：O(Nlog⁡k)

因此，总的时间复杂度为： O(klog⁡k+Nlog⁡k)

由于 klog⁡k在大多数情况下远小于 Nlog⁡k，通常可以简化为： O(Nlog⁡k)

空间复杂度分析

最小堆：堆中最多包含 k 个节点（即每个链表的当前最小节点）。
结果链表：需要额外的空间来存储合并后的链表，但这是输出的一部分，不计入额外空间复杂度。

因此，空间复杂度主要由最小堆决定，为： O(k)

总结

时间复杂度：O(Nlog⁡k)
空间复杂度：O(k)

【C++】LeetCode：LCR 078. 合并 K 个升序链表

题干：