当前位置:网站首页>[offer78]合并多个有序链表
[offer78]合并多个有序链表
2022-07-06 09:17:00 【劲腰傩舞】
合并多个有序链表
题目
给定一个链表数组,每个链表都已经按升序排列。
请将所有链表合并到一个升序链表中,返回合并后的链表。
示例 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
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/vvXgSW
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
/*方法:优先队列*/
#include <vector>
#include<queue>
#include<iostream>
using namespace std;
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) {
}
};
/*预备知识:函数对象、类模板、匿名对象、单链表头结点的作用、priorty_queue基本操作*/
/*一。优先队列(priority_queue)的初始化需要使用到函数对象,作用是设置如何判断堆中两个元素的优先级大小,默认使用less<T>()*/
/*二。可以充当函数对象的东西:普通函数、重载了()的类 * 1.使用普通函数:直接传入函数名 * 2.使用类:传入该类的一个对象,一般使用匿名对象,即类名() * 3.传入优先级队列的函数对象需要和所要求的格式一致。 */
/*三。查看prior_queue的模板的话,后两个参数类型是有默认值的 * 如果使用默认类型。需要在自定义类中自行实现对<的重载 */
/*准备函数对象*/
struct cmp {
bool operator ()(ListNode* a, ListNode* b) {
/*返回true的情况下,该元素在堆中下移*/
return a->val > b->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
/*思路就是把所有的指针都放在一个优先队列中 * 堆顶存放优先级最高的。 * 每次弹出堆顶 * 再判断其是否还有后续结点,如果有,在push进来,优先队列重新调整堆的结构 */
priority_queue<ListNode*,vector<ListNode*>,cmp> queue;
for (auto node : lists) {
/*题目中已经说明可能会传入空链表了*/
if (node)
queue.push(node);
}
/*定义结果存放位置,先定义头结点,及其对应的指针(为了统一操作)*/
ListNode ans, * cur=&ans;
/*最终的情况就是队列为空*/
while (!queue.empty()) {
/*不用想直接一步pop,pop没有返回值*/
ListNode* temp = queue.top();
queue.pop();
/*直接操作头指针,将取出的temp接到ans后面*/
cur->next = temp;
/*移动指针到链表末端,以便继续拼接*/
cur = cur->next;
if (temp->next)
queue.push(temp->next);
}
/*头结点没有实际意义。不用返回*/
return ans.next;
}
};
边栏推荐
- Imgcat usage experience
- Mysqldump error1066 error solution
- Use of lists
- Inline detailed explanation [C language]
- Postman 中级使用教程【环境变量、测试脚本、断言、接口文档等】
- Basic operations of databases and tables ----- creating data tables
- Gravure sans fil Bluetooth sur micro - ordinateur à puce unique
- Kconfig Kbuild
- Esp8266 connects to bafayun (TCP maker cloud) through Arduino IED
- VSCode基础配置
猜你喜欢
open-mmlab labelImg mmdetection
VSCode基础配置
Learning notes of JS variable scope and function
程序设计大作业:教务管理系统(C语言)
Redis cache update strategy, cache penetration, avalanche, breakdown problems
JS variable types and common type conversions
Basic knowledge of lithium battery
Kaggle competition two Sigma connect: rental listing inquiries (xgboost)
(三)R语言的生物信息学入门——Function, data.frame, 简单DNA读取与分析
Single chip Bluetooth wireless burning
随机推荐
Cannot change version of project facet Dynamic Web Module to 2.3.
单片机蓝牙无线烧录
Custom view puzzle getcolor r.color The color obtained by colorprimary is incorrect
数据库课程设计:高校教务管理系统(含代码)
ARM PC=PC+8 最便于理解的阐述
ESP学习问题记录
Basic operations of databases and tables ----- creating data tables
@The difference between Autowired and @resource
AMBA、AHB、APB、AXI的理解
[leetcode19]删除链表中倒数第n个结点
Pytoch implements simple linear regression demo
Working principle of genius telephone watch Z3
Selective sorting and bubble sorting [C language]
Inline detailed explanation [C language]
CUDA C programming authoritative guide Grossman Chapter 4 global memory
Detailed explanation of truncate usage
Priority inversion and deadlock
(三)R语言的生物信息学入门——Function, data.frame, 简单DNA读取与分析
MySQL时间、时区、自动填充0的问题
NRF24L01故障排查