23. 合并K个升序链表

解题思路:两种解法,一种优先级队列,一种分治
优先级队列解法:以节点中存储的值进行排序
依次遍历所有的链表,把链表中的节点加入到优先级队列中
依次从优先级队列的弹出并删除最小的元素加入到新的链表中,直到队列为空,
返回新的链表
AC代码:
class Solution {public static ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((first,second)->first.val-second.val);for (ListNode list : lists) {while (list!=null){queue.add(list);list=list.next;}}ListNode result = new ListNode();ListNode tem = result;while (queue.size()!=0){ListNode node =queue.remove();tem.next =node;tem=tem.next;}tem.next=null;//防止出现循环链,a->b->areturn result.next;}
}分治:类似与归并排序的思想
如果链表的长度大于2:继续对链表进行拆分成两部分,继续使用分治的思想
将链表数组数组分成两半,list[0,left]和list[left,end],分别对这对两部分进行分治排序合并,这两部分排序后的结果first,second
然后对first和second这两个链表进行双链表合并排序,合并思路:双指针:因为两个链表有序,所以只需要依次比较两个元素的大小,然后添加到新的链表中即可
first指针指向第一个链表,second指针指向第二个链表,result保存合并后的链表的头节点的前驱,tail初值指向result
如果fist和second当前指向的节点都不为null,循环遍历:
如果first.val<second.value,tail.next=first,first=first.next,tail=tail.next
否则,tail.next=second,second=second.next,tail=tail.next
循环结束之后,那么first和second只会有一个节点不为null,因为原链表已经有序,所以只需要将不为null的哪个链表添加到prev.next中即可
最终result.next即为合并后链表的第一个节点
如果链表的长度等于1:不需要分治合并,直接返回该链表即可
AC代码:
class Solution {public static ListNode mergeKLists(ListNode[] lists) {if (lists==null||lists.length==0){return null;}return merge(lists,0,lists.length-1);}//对list[left,right]范围的链表进行合并,返回合并后新的链表public static ListNode merge(ListNode[] lists,int left,int right){if (left==right){return lists[left];}int mid = (left+right)/2;ListNode first = merge(lists,left,mid);//对左半部的链表分进行分治合并,返回合并后的结果ListNode second = merge(lists,mid+1,right);//对右半部分的链表进行分治合并,返回合并后的结果ListNode result = sortMerge(first,second);//对first和second进行双链表合并return result;}public static ListNode sortMerge(ListNode first,ListNode second){ListNode result = new ListNode();ListNode tail = result;while (first!=null&&second!=null){if (first.val<second.val){tail.next= first;first=first.next;}else {tail.next=second;second=second.next;}tail = tail.next;}tail.next=(first==null)?second:first;return result.next;}
}
相关文章:
23. 合并K个升序链表
解题思路:两种解法,一种优先级队列,一种分治优先级队列解法:以节点中存储的值进行排序依次遍历所有的链表,把链表中的节点加入到优先级队列中依次从优先级队列的弹出并删除最小的元素加入到新的链表中,直到…...
软中断与tasklet简介
一、软中断 1.1 何为软中断? Linux 系统为了解决中断处理程序执行过长的问题,将中断过程分成了两个阶段,分别是「上半部(Top Half)和下半部分(Bottom Half)」。 上半部用来快速处理中断。一…...
JUC 之 线程阻塞工具 LockSupport
——LockSupport 与 线程中断 线程中断机制 一个线程不应该由其他线程来强制中断或停止,而是应该由线程自己自行停止,所以,Thread.stop,Thread.suspend,Thread.resume 都已经被废弃 在 Java 中没有办法立即停止一条线…...
常用数据结构总结-Java版
常用数据结构总结(Java版) C/Java/Python 数据结构大比较 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Dokzp1HQ-1677329125447)(assets/image-20220116142815859.png)] array 同一种类型数据的集合,其实数组…...
【基础算法】二分例题(我在哪?)
🌹作者:云小逸 📝个人主页:云小逸的主页 📝Github:云小逸的Github 🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前…...
怕上当?来看这份网络钓鱼和诈骗技术趋势
网络钓鱼和诈骗:当前的欺诈类型 网络钓鱼 钓鱼者可以攻击任何在线服务——银行、社交网络、政府门户网站、在线商店、邮件服务、快递公司等——中的证书。但是,顶级品牌的客户往往面临更大风险,因为相比小品牌,人们更喜欢使用和…...
2023年全国最新保安员精选真题及答案6
百分百题库提供保安员考试试题、保安职业资格考试预测题、保安员考试真题、保安职业资格证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 61.关于保安员职业资格条件说法正确的是()。 A:必须考试合格…...
unity热更新新方案,ILRuntime
ILRuntime 是一个独立的、跨平台的 .NET Runtime,可用于在 Unity 中实现热更功能。使用 ILRuntime,您可以在游戏运行时加载和执行 C# 脚本,而不需要重新编译整个项目。 以下是一些使用 ILRuntime 的基本步骤: 在 Unity Asset St…...
【J1】【队列】报数游戏
题目描述 有 n 个小朋友围成一圈玩游戏,小朋友从 1 至 n 编号,2 号小朋友坐在 1 号小朋友的顺时针方向,3 号小朋友坐在 2 号小朋友的顺时针方向,……,1 号小朋友坐在 n 号小朋友的顺时针方向。 游戏开始,…...
《程序员的自我修养》阅读笔记
文章目录【第2部分】静态链接1 编译过程2 编辑器的工作流程3 链接——模块的拼接4 目标文件目标文件中的段(section)ELF文件结构5 静态链接1 空间与地址分配2 符号解析与重定位【第3部分】装载与动态链接1 装载的方式2 进程的启动3 为什么需要动态链接&a…...
【跟着ChatGPT学深度学习】ChatGPT带我入门深度学习
❤️觉得内容不错的话,欢迎点赞收藏加关注😊😊😊,后续会继续输入更多优质内容❤️👉有问题欢迎大家加关注私戳或者评论(包括但不限于NLP算法相关,linux学习相关,读研读博…...
软工2023个人作业一——阅读和提问
项目内容这个作业属于哪个课程2023年北航敏捷软件工程这个作业的要求在哪里个人作业-阅读和提问我在这个课程的目标是学习并掌握现代软件开发和项目管理技术,体验敏捷开发工作流程这个作业在哪个具体方面帮助我实现目标通读《构建之法》,了解软件工程中基…...
【Redis】线程模型:Redis是单线程还是多线程?
【Redis】线程模型:Redis是单线程还是多线程? 文章目录【Redis】线程模型:Redis是单线程还是多线程?Redis 是单线程吗?Redis 单线程模式是怎样的?Redis 采用单线程为什么还这么快?Redis 6.0 之前…...
FSM(有限状态机)
FSM有限状态机FSM创建控制有限状态机的脚本设置FSM状态机下的各个状态添加测试类FSM的优点FSM 虽然Unity已经有了动画状态机,但是为了代码的开放封闭原则,这时FSM有限状态机的作用就凸显了出来。 创建控制有限状态机的脚本 先创建一个脚本用来控制有限…...
奇妙的background-clip:text
我们在学习CSS3时,一个背景属性background-clip用来对背景进行裁剪,即指定背景绘制的区域,通常我们使用的几个属性如下:值说明border-box默认值。背景绘制在边框方框内(剪切成边框方框)。padding-box背景绘…...
Vmware虚拟机无法联通主机解决方法二
昨天在遇到了VMware 虚拟机无法联通主机,导致我在CentOS-7 搭建的伪Hadoop3 服务,无法访问管理平台,使用将网络编辑器修改为“桥接”模式解决。今天在学习HBase 时,昨天的问题又重新了,我通过SSH 工具MobaXterm 都无法…...
Boost资料整理备忘
Boost资料整理备忘 网络资源 书籍: The Boost C Libraries官方文档 Boost Library Documentation random boost.randomBoost随机库的简单使用:Boost.Random(STL通用)tutorialstd::random boost::asio Boost.Asio 网络编程 - 基本原理Boost.Asio DocBoost定时器 网…...
规则引擎与风控系统01:新问题,新挑战
如果说在支付系统中使用设计模式,以及开发自定义协议的物联网这两类应用还不够酷的话,那么接下来,咱们就来学一点高逼格的技术吧。 在互联网已经日益普遍的时代,不管是开发2C应用还是2B应用,相信大部分的开发者都有过处理复杂业务逻辑的经历,比如电商、社交、电子政务、O…...
Oracle-00-卸载篇
这里给出企业级的Oracle 10g的卸教程,新安装的19c并没有正经去做卸载的操作,为了后面教程的进度,这里就先借用下10g,如果有需要会重新更新19c的卸载教程 windows服务中将Oracle所有服务全部停掉 选中Oracle - OraDb10g_home2->Oracle Installation Products->Univers…...
Java线程池使用与原理解析1(线程池优点、使用方法、参数含义及线程池运转机制)
为什么要使用线程池? JDK1.5后JUC包添加了线程池相关接口,在Java诞生之初并没有线程池这个概念。刚开始Java程序都是自行创建线程去处理任务。随着应用使用的线程越来越多,JDK开发者们发现有必要使用一个统一的类来管理这些线程,…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
LeetCode 0386.字典序排数:细心总结条件
【LetMeFly】386.字典序排数:细心总结条件 力扣题目链接:https://leetcode.cn/problems/lexicographical-numbers/ 给你一个整数 n ,按字典序返回范围 [1, n] 内所有整数。 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。…...
SAP学习笔记 - 开发24 - 前端Fiori开发 Filtering(过滤器),Sorting and Grouping(排序和分组)
上一章讲了SAP Fiori开发的表达式绑定,自定义格式化等内容。 SAP学习笔记 - 开发23 - 前端Fiori开发 Expression Binding(表达式绑定),Custom Formatters(自定义格式化)-CSDN博客 本章继续讲SAP Fiori开发…...
springboot启动mapper找不到方法对应的xml
数据源配置 目录结构 idea中mapper.java 可以找到对应的mapper.xml文件 启动却找不到 因为mapper.db1会被识别为文件名 而非目录结构 调整为这种...
基于单片机的病房呼叫系统(源码+仿真)
该系统由以 STM32F4 为平台的监控终端以及以 CC2530 为平台的无线传感网组成。系统上电后自动完成 ZigBee 网络的组建、终端节点的加入,病人可利用便携式的病人终端发出呼叫求助请求信息、节点在线信息以及对护士的服务评价信息等,这些信息通过路由节点发…...
【CSS-7】深入解析CSS伪类:从基础到高级应用
CSS伪类是前端开发中不可或缺的强大工具,它们允许我们根据文档树之外的信息或简单选择器无法表达的状态来样式化元素。本文将全面探讨CSS伪类的各种类型、使用场景和最佳实践。 1. 伪类基础概念 1.1 什么是伪类? 伪类(Pseudo-class&#x…...
