当前位置:网站首页>[offer78] merge multiple ordered linked lists
[offer78] merge multiple ordered linked lists
2022-07-06 12:24:00 【Vigorous waist Nuo dance】
Merge multiple ordered linked lists
subject
Given a linked list array , Each list has been listed in ascending order .
Please merge all linked lists into one ascending linked list , Return the merged linked list .
Example 1:
Input :lists = [[1,4,5],[1,3,4],[2,6]]
Output :[1,1,2,3,4,4,5,6]
explain : The linked list array is as follows :
[
1->4->5,
1->3->4,
2->6
]
Combine them into an ordered list to get .
1->1->2->3->4->4->5->6
Example 2:
Input :lists = []
Output :[]
Example 3:
Input :lists = [[]]
Output :[]
Tips :
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] Press Ascending array
lists[i].length The sum of is not more than 10^4
source : Power button (LeetCode)
link :https://leetcode.cn/problems/vvXgSW
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
/* Method : Priority queue */
#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) {
}
};
/* Preliminary knowledge : Function object 、 Class template 、 Anonymous object 、 The function of single chain header node 、priorty_queue Basic operation */
/* One . Priority queue (priority_queue) Initialization of requires the use of function objects , The function is to set how to judge the priority size of two elements in the heap , By default less<T>()*/
/* Two . Something that can act as a function object : Ordinary function 、 Reload the () Class * 1. Use normal functions : Pass in the function name directly * 2. Use class : Pass in an object of this class , Anonymous objects are generally used , That is, the class name () * 3. The function object passed into the priority queue needs to be consistent with the required format . */
/* 3、 ... and . see prior_queue If you have a template , The last two parameter types have default values * If you use the default type . You need to implement the < overloaded */
/* Prepare the function object */
struct cmp {
bool operator ()(ListNode* a, ListNode* b) {
/* return true Under the circumstances , This element moves down in the heap */
return a->val > b->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
/* The idea is to put all pointers in a priority queue * The top of the heap has the highest priority . * Every time the top of the stack is ejected * Then judge whether there are subsequent nodes , If there is , stay push Come in , Priority queues restructure the heap */
priority_queue<ListNode*,vector<ListNode*>,cmp> queue;
for (auto node : lists) {
/* It has been stated in the title that an empty linked list may be introduced */
if (node)
queue.push(node);
}
/* Define the storage location of results , First define the header node , And its corresponding pointer ( For unified operation )*/
ListNode ans, * cur=&ans;
/* The final situation is that the queue is empty */
while (!queue.empty()) {
/* Don't think about taking a direct step pop,pop no return value */
ListNode* temp = queue.top();
queue.pop();
/* Direct operation head pointer , To take out temp Receive ans Back */
cur->next = temp;
/* Move the pointer to the end of the linked list , In order to continue splicing */
cur = cur->next;
if (temp->next)
queue.push(temp->next);
}
/* The header node has no practical significance . Don't go back */
return ans.next;
}
};
边栏推荐
- C language callback function [C language]
- Several declarations about pointers [C language]
- ESP learning problem record
- Redis based distributed locks and ultra detailed improvement ideas
- Arduino get random number
- Kconfig Kbuild
- Expected value (EV)
- (3) Introduction to bioinformatics of R language - function, data Frame, simple DNA reading and analysis
- JS regular expression basic knowledge learning
- (四)R语言的数据可视化——矩阵图、柱状图、饼图、散点图与线性回归、带状图
猜你喜欢
js 变量作用域和函数的学习笔记
基於Redis的分布式ID生成器
Fashion Gen: the general fashion dataset and challenge paper interpretation & dataset introduction
JS正则表达式基础知识学习
A possible cause and solution of "stuck" main thread of RT thread
Gravure sans fil Bluetooth sur micro - ordinateur à puce unique
Expected value (EV)
数据库课程设计:高校教务管理系统(含代码)
ES6语法总结--上篇(基础篇)
Working principle of genius telephone watch Z3
随机推荐
Minio file download problem - inputstream:closed
Esp8266 connects to bafayun (TCP maker cloud) through Arduino IED
JS变量类型以及常用类型转换
【ESP32学习-2】esp32地址映射
E-commerce data analysis -- salary prediction (linear regression)
(一)R语言入门指南——数据分析的第一步
1081 rational sum (20 points) points add up to total points
C language, log print file name, function name, line number, date and time
Pytoch implements simple linear regression demo
(3) Introduction to bioinformatics of R language - function, data Frame, simple DNA reading and analysis
ORA-02030: can only select from fixed tables/views
Redis 缓存更新策略,缓存穿透、雪崩、击穿问题
[Nodejs] 20. Koa2 onion ring model ----- code demonstration
[899]有序队列
(三)R语言的生物信息学入门——Function, data.frame, 简单DNA读取与分析
imgcat使用心得
Arduino uno R3 register writing method (1) -- pin level state change
RuntimeError: cuDNN error: CUDNN_ STATUS_ NOT_ INITIALIZED
MySQL时间、时区、自动填充0的问题
Reno7 60W super flash charging architecture