本文涉及知识点
堆 优先队列
LeetCode23. 合并 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 <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] 按 升序 排列
lists[i].length 的总和不超过 104
堆(优先队列)
n = ∑ l i s t s [ i ] . l e n g t h \sum lists[i].length ∑lists[i].length
暴力做法:将数据全部放到大根堆,从链表尾部开始拼接。时间复杂度: O(nlogn)
进阶的做法:
由于链表是有序的,那新链表的新元素一定是旧链表没有处理的首元素。
用 小根堆,存储 lists首元素的值,和指针。
出栈:
栈顶元素,并加到新栈尾部。
如果栈顶元素的next非空,则将next加到堆中。
时间复杂度:O(nlogk)
代码
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<pair<int,ListNode*>, vector<pair<int, ListNode*>>, std::greater<>> heap;for (auto& p : lists) {if( nullptr == p){continue;}heap.emplace(make_pair(p->val, p));}ListNode* head = nullptr, *tail = nullptr;while (heap.size()) {auto [val, p] = heap.top();heap.pop();if (nullptr == head) {head = tail = new ListNode(val);}else {tail->next = new ListNode(val);tail = tail->next;}if (nullptr != p->next ) {p = p->next;heap.emplace(make_pair(p->val, p));}}return head;}
};
扩展阅读
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关推荐
我想对大家说的话 |
---|
《喜缺全书算法册》以原理、正确性证明、总结为主。 |
按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。