LCR 078. 合并 K 个升序链表 - 力扣LeetCodeLCR 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) {} * }; */ #includequeue class Solution { public: struct cmp { bool operator()(const ListNode* l1, const ListNode* l2) { // priority\_queue小根堆规则返回truel1放下面 return l1-val l2-val; } } ; ListNode* mergeKLists(vectorListNode* lists) { int nlists.size(); //创建小根堆 priority_queueListNode*, vectorListNode*,cmp minHeap; //让所有的头节点进入小根堆 for(auto l :lists) if(l) minHeap.push(l); //合并k个有序链表 ListNode*retnew ListNode(0); ListNode*prevret; while(!minHeap.empty()) { ListNode* tminHeap.top(); minHeap.pop(); prev-nextt; prevt; if(t-next) minHeap.push(t-next); } prevret-next; delete ret; return prev; } };
算法日常・每日刷题--＜链表＞4
LCR 078. 合并 K 个升序链表 - 力扣LeetCodeLCR 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) {} * }; */ #includequeue class Solution { public: struct cmp { bool operator()(const ListNode* l1, const ListNode* l2) { // priority\_queue小根堆规则返回truel1放下面 return l1-val l2-val; } } ; ListNode* mergeKLists(vectorListNode* lists) { int nlists.size(); //创建小根堆 priority_queueListNode*, vectorListNode*,cmp minHeap; //让所有的头节点进入小根堆 for(auto l :lists) if(l) minHeap.push(l); //合并k个有序链表 ListNode*retnew ListNode(0); ListNode*prevret; while(!minHeap.empty()) { ListNode* tminHeap.top(); minHeap.pop(); prev-nextt; prevt; if(t-next) minHeap.push(t-next); } prevret-next; delete ret; return prev; } };
