首页 > 其他分享 >23. 合并 K 个升序链表

23. 合并 K 个升序链表

时间:2023-09-19 22:01:22浏览次数:55  
标签:ListNode cur 23 lists 链表 升序 minHeap

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

 

示例 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
class Solution {
public:
   ListNode* mergeKLists(vector<ListNode*>& lists) {
       auto cmp = [](ListNode* a, ListNode* b){return a->val > b->val;};
       priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> minHeap(cmp);
       for(int i = 0; i < lists.size(); ++i){
           while(lists[i]){
               minHeap.push(lists[i]);
               lists[i] = lists[i]->next;
           }
       }
       if(minHeap.empty()) return nullptr;
       ListNode* res = minHeap.top();
       ListNode* cur = res;
       minHeap.pop();
       while(!minHeap.empty()){
           cur->next = minHeap.top();
           minHeap.pop();
           cur = cur->next;
       }
       cur->next = nullptr;
       return res;
   }
};

标签:ListNode,cur,23,lists,链表,升序,minHeap
From: https://blog.51cto.com/u_15862486/7529757

相关文章

  • 9.19单链表带哨兵和双向链表带哨兵
    1.单链表publicclassMain{publicstaticvoidmain(String[]args){LNodeL=newLNode();L.addFirst(4);//头插L.addFirst(3);L.addFirst(2);L.addFirst(1);L.addLast(5);//尾插L.Isempty();//判空L.......
  • P9545 [湖北省选模拟 2023] 环山危路 / road
    题意就是给定一个竞赛图,多次询问,每次询问有多个源点\(s_1,s_2,\cdotss_k\),单个汇点\(t\),一条边流量为\(1\),求最大流。考虑转成最小割,相当于将\(V\)划分成两个集合\(S,T\),\(S\cupT=V\)且\(S\capT=\varnothing\),\(s_i\inS,t\inT\),然后令\(f(S,T)=\sum\limits_{u\inS......
  • 2023.9.19——每日总结
    学习所花时间(包括上课):9h代码量(行):0行博客量(篇):1篇今天,上午上课,下午做任务。我了解到的知识点:1.了解了关于模型训练的一些知识和注意事项;明日计划:1.上课;2.比赛;......
  • 每日总结20230919
    代码时间(包括上课)5h代码量(行):30行博客数量(篇):1篇相关事项:1、今天上午上的是软件设计模式和人机交互技术,软件设计模式讲的是单例模式和适配器模式,人机交互技术讲的是定位。2、今天上午人机交互技术留了三十分钟小组讨论明天软件案例开发分析的PPT讲解。3、晚上和下午的话去科技......
  • 20230918
    早上用JavaFX完成验证码登陆页面的作业,学会了使用scenebuilder创建窗口的fxml布局文件遇到了问题,发现是使用的simplecaptcha生成的验证码图片为BufferdImage类型转换成JavaFX使用的Image类型中出现的问题,最后解决了。踩了些坑之后自我感觉还行,但是没什么用。下午王老......
  • 20230919打卡
    今天的学习重点是链表合并和多项式创建。链表合并是算法与数据结构中的重要内容,它可以将两个有序链表合并成一个有序链表。通过学习链表合并的原理和实现方法,我掌握了如何有效地处理链表数据结构,并能够理解和运用链表相关的算法。另外,我还学习了多项式的创建。多项式是数学中的重......
  • 日常记录--day6--2023-9月19日--周二
    日程:今天只有上午有课,7点20起床,吃了个早饭去上课,早上有一节数据结构,复习了一下链表,学了栈和队列。中午小睡一个小时,下午起来学习了一会Java,晚上7-8点听了下代码随想路,8-9点继续力扣。学了什么:Java让人头疼,晚上练了道动态规划,有点不太会,复习了数据结构。PS:不想学习,想要成为插线......
  • 23.9.19
    学习了HTML相关知识1、标签<h1>....</h1>(h1->h6重要程度依次降低)标签都是定义好的,不能自己随意定义2、水平线标签<hr>3、图片标签  <imgsrc="..."width="..."height="...">绝对路径:绝对磁盘路径(D:/xxx)、绝对网络路径(https://xxxx)相对路径:从当前文件开始查找。(./......
  • 2023.9.18
    //高精度//注:大写字母代表位数大于(1e6),小写字母代表小于(1e6)的数//在存储较大数时,用数组来记录每一位的数字,数组下标为0,则记录大数的个位,依次往后推##A+Bc++#include<iostream>#include<vector>usingnamespacestd;vector<int>add(vector<int>&A,vector<int>&B)......
  • 2023.9.19 二年级四则运算在线答题
    packageTest2333;importjava.util.Random;importjava.util.Timer;importjava.util.TimerTask;importjava.util.Scanner;publicclassdaily1{//设置时长(秒)staticintcountDownTime=100;publicstaticvoidmain(String[]args){Scannersc=n......