算法日常・每日刷题--＜链表＞4
LCR 078. 合并 K 个升序链表 - 力扣（LeetCode）LCR 078. 合并 K 个升序链表 - 给定一个链表数组，每个链表都已经按升序排列。请将所有链表合并到一个升序链表中，返回合并后的链表。 示例 1：输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6示例 2：输入：lists = []输出：[]示例 3：输入：lists = [[]]输出：[] 提示： * k == lists.length * 0 <= k <= 10^4 * 0 <= lists[i].length <= 500 * -10^4 <= lists[i][j] <= 10^4 * lists[i] 按 升序 排列 * lists[i].length 的总和不超过 10^4 注意：本题与主站 23 题相同： https://leetcode.cn/problems/merge-k-sorted-lists/ [https://leetcode.cn/problems/merge-k-sorted-lists/]![]()
https://leetcode.cn/problems/vvXgSW/
题目描述
给定一个链表数组，每个链表都已经按升序排列。 请将所有链表合并到一个升序链表中，返回合并后的链表。
示例： 输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]
核心难点：多条有序链表多路归并，如何高效持续拿到全局最小值节点。
思路分析
多条升序链表，每一条链表头部都是当前链表最小值。我们需要不断从所有链表头部选出全局最小节点接入结果链表。 暴力思路：每次遍历全部链表头寻找最小值，时间复杂度 \(O(kN)\)，效率低下。
优化方案：小根堆（优先队列）
- 将所有非空链表的头节点放入小根堆；堆自动维护堆顶为全局最小值；
- 循环取出堆顶最小节点，接入结果链表；
- 如果取出的节点存在后继节点，将后继节点推入堆；
- 堆为空时，全部节点处理完毕，返回合并链表。
/** * 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) {} * }; */ #include<queue> class Solution { public: struct cmp { bool operator()(const ListNode* l1, const ListNode* l2) { // priority\_queue小根堆规则：返回true，l1放下面 return l1->val > l2->val; } } ; ListNode* mergeKLists(vector<ListNode*>& lists) { int n=lists.size(); //创建小根堆 priority_queue<ListNode*, vector<ListNode*>,cmp > minHeap; //让所有的头节点进入小根堆 for(auto l :lists) if(l) minHeap.push(l); //合并k个有序链表 ListNode*ret=new ListNode(0); ListNode*prev=ret; while(!minHeap.empty()) { ListNode* t=minHeap.top(); minHeap.pop(); prev->next=t; prev=t; if(t->next) minHeap.push(t->next); } prev=ret->next; delete ret; return prev; } };