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

题干：

给定一个链表数组，每个链表都已经按升序分列。
请将所有链表归并到一个升序链表中，返回归并后的链表。
 
解法：优先队列

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     ListNode *next;
6. *     ListNode() : val(0), next(nullptr) {}
7. *     ListNode(int x) : val(x), next(nullptr) {}
8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9. * };
10. */
11. auto cmp = [](ListNode*a,ListNode*b){
12.     return a->val>b->val;
13. };
14. class Solution {
15. public:
16.          ListNode * mergeTwoLists(ListNode * a,ListNode * b){
17.             ListNode * dummy = new ListNode(0);
18.             ListNode * cur = dummy;
19.             while (a!= nullptr&&b!= nullptr){
20.                 if (a->val<b->val){
21.                     cur->next = a;
22.                     a = a->next;
23.                 } else{
24.                     cur->next = b;
25.                     b = b->next;
26.                 }
27.                 cur = cur->next;
28.             }
29.             cur->next = (a== nullptr)?b:a;
30.             return dummy->next;
31.         };
33.         ListNode *mergeKLists(std::vector<ListNode*>& lists){
35.             std::priority_queue<ListNode*,std::vector<ListNode*>, decltype(cmp)> minHeap(cmp);
37.             for (auto list:lists) {
38.                 if(list!= nullptr){
39.                     minHeap.push(list);
40.                 }
41.             }
43.             ListNode dummy = ListNode(0);
44.             ListNode * tail = &dummy;
46.             while (!minHeap.empty()){
47.                 ListNode * miniNode = minHeap.top();
48.                 minHeap.pop();
50.                 tail->next = miniNode;
51.                 tail = tail->next;
53.                 if (miniNode->next!= nullptr){
54.                     minHeap.push(miniNode->next);
55.                 }
56.             }
57.             return  dummy.next;
58.         };
59. };

复制代码

举例分步解析：

示例：归并三个升序链表

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

• 链表 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)
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。