leetcode：23. 合并K个升序链表

题目

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例：

  1. 输入：lists = [[1,4,5],[1,3,4],[2,6]]
  2. 输出：[1,1,2,3,4,4,5,6]
  3. 解释：链表数组如下：
  4. [
  5.   1->4->5,
  6.   1->3->4,
  7.   2->6
  8. ]
  9. 将它们合并到一个有序链表中得到。
  10. 1->1->2->3->4->4->5->6
  1. 输入：lists = []
  2. 输出：[]
  1. 输入：lists = [[]]
  2. 输出：[]

解答 & 代码

解法一：小根堆（优先队列实现）

每次合并，都应该选择当前各个链表剩余部分最前面的节点的值的大小，选择值最小的节点插入。
问题就在于如何得到值最小的节点？可以用小根堆来存储各个链表剩余部分最前面的节点。

优先队列 priority_queue：

  • 头文件：#include <queue>
  • 定义：priority_queue<Type, Container, Functional>
    • 大根堆：priority_queue<int> maxHeap or priority_queue<int, vector<int>, less<int>> maxHeap
    • 小根堆：priority_queue<int, vector<int>, greater<int>> minHeap
    • 自定义类型：如下面代码所示
  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. class Solution {
  12. private:
  13.     // 小根堆的回调函数
  14.     struct cmp {
  15.         bool operator() (ListNode* node1, ListNode* node2) {
  16.             return node1->val > node2->val;
  17.         }
  18.     };
  19. public:
  20.     ListNode* mergeKLists(vector<ListNode*>& lists) {
  21.           // 小根堆（基于优先队列）
  22.         priority_queue<ListNode*, vector<ListNode*>, cmp> minHeap;
  23.           // 初始将每个链表的头节点（如果不为空）存入小根堆
  24.         for(int i = 0; i < lists.size(); ++i)
  25.         {
  26.             if(lists[i] != nullptr)
  27.                 minHeap.push(lists[i]);
  28.         }
  30.         ListNode* dummyHead = new ListNode();
  31.         ListNode* pre = dummyHead;
  32.         while(!minHeap.empty())
  33.         {
  34.             ListNode* minNode = minHeap.top();
  35.             minHeap.pop();
  36.             pre->next = minNode;
  37.             pre = pre->next;
  38.             if(minNode->next != nullptr)
  39.                 minHeap.push(minNode->next);
  40.         }
  42.         return dummyHead->next;
  43.     }
  44. };

复杂度分析：设一共 K 个链表，这 K 个链表节点总数为 N

  • 时间复杂度 O(N × logK)：优先队列中元素不超过 K 个，因此插入和删除时间代价为 O(logK)，N 个节点都会插入优先队列并删除一次
  • 空间复杂度 O(K)：优先队列中的元素不超过 K 个

执行结果：

  1. 执行结果：通过
  3. 执行用时：20 ms, 在所有 C++ 提交中击败了 79.35% 的用户
  4. 内存消耗：12.9 MB, 在所有 C++ 提交中击败了 74.70% 的用户

其他解法

[困难] 23. 合并K个升序链表