【Day6】合并两个排序链表与合并k个已排序的链表,java代码实现
前言:
大家好,我是良辰丫🚀🚀🚀,今天与大家一起做两道牛客网的链表题
,好久写关于链表题的博客了,这两道题可以帮大家巩固一下链表知识,我把两道题的链接放到下面,大家可以去做一下。💥💟💟💥
题目链接:
合并两个排序链表
合并K个排序链表
🧑个人主页:良辰针不戳
📖所属专栏:EveryDay学java
🍎励志语句:生活也许会让我们遍体鳞伤,但最终这些伤口会成为我们一辈子的财富。
💦期待大家三连,关注,点赞,收藏。
📜作者能力有限,也会出错,希望大家可以指正。
💞愿与君为伴,共探Java汪洋大海。
目录
- 1、合并两个排序链表
- 1.1 题目描述
- 1.2 实例
- 1.3 题目分析
- 1.4 代码展示
- 2、合并K个排序链表
- 2.1 题目描述
- 2.2 实例
- 2.3 题目分析
- 2.4 代码展示与分析
1、合并两个排序链表
1.1 题目描述
- 输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。
- 数据范围: 0 \le n \le 10000≤n≤1000,-1000 \le 节点值 \le 1000−1000≤节点值≤1000
要求:空间复杂度 O(1)O(1),时间复杂度 O(n)O(n)- 如输入{1,3,5},{2,4,6}时,合并后的链表为{1,2,3,4,5,6},所以对应的输出为{1,2,3,4,5,6},转换过程如下图所示:
1.2 实例
输入:
{1,3,5},{2,4,6}
返回值:
{1,2,3,4,5,6}
1.3 题目分析
做题不能着急,一定先要读懂题。
这个题目的要求是合并两个有序链表,而且合并后的链表也是有序的。
做题要学的是思想,今天我们主要用到的是虚拟节点。
- 申请一个虚拟的头结点
- cur指向这个虚拟头结点
- while循环进行进行遍历,只要其中一个链表为空结束循环
- 循环里面进行判断,list1和list2谁较小就与cur进行拼接
- 结束循环后,说明至少有一个链表为空,因此,cur拼接不为空的链表;也可能两个都为空,至少拼接一个,因为链表要以null结束。
1.4 代码展示
下面是具体代码,我也会稍微写一点注释帮助大家理解。
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {//申请虚拟节点ListNode newHead = new ListNode(-1);//cur指向当前的虚拟节点ListNode cur = newHead;//while循环,只要遍历完其中一个链表就结束循环while(list1 != null && list2 != null){if (list1.val < list2.val){//拼接cur.next = list1;cur = cur.next;list1 = list1.next;} else {//拼接cur.next = list2;cur = cur.next;list2 = list2.next; }}//拼接不为空的,两个都遍历完的时候任意拼接一个if(list1 != null){cur.next = list1;}else{cur.next = list2;}return newHead.next;}
}
2、合并K个排序链表
聪明的大家或许已经发现,这道题是刚刚那道题的升级版,牛客网标注着难题的标志,其实也没那么难,找到了规律,掌握了思想,做起来很容易。
2.1 题目描述
- 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
- 数据范围:节点总数 0 \le n \le 50000≤n≤5000,每个节点的val满足 |val| <= 1000∣val∣<=1000
要求:时间复杂度 O(nlogn)O(nlogn)
2.2 实例
输入:
[{1,2},{1,4,5},{6}]
返回值:
{1,1,2,4,5,6}
2.3 题目分析
做题除了要看懂题,还要注意思想,不要忙于去做题。
先去分析,想明白用什么方法去做。
首先大家肯定会想到粗鲁的办法,从前往后,依次遍历比较,然后进行拼接,这样不仅时间复杂度高,而且比较麻烦,搞的头晕目眩,也不一定能得出正确的答案。那么我们需要想到另一种方法,分治思想,这种思想我们在快排和归并排序中见过,既然接触过,我们肯定有点基础,我们来回忆一下所谓的分治思想。
分治
就是分而治之,可以这样理解,解决一个大问题的时候,首先把大问题化解成若干个小问题(小问题与大问题的性质保持一致),逐个解决完小问题,然后合并,最终就解决了所谓的大问题。
总结分治思想:
- 大问题化解为若干个子问题。
- 计算各个子问题。
- 合并所有子问题的解。
看到这里,大家应该对分治思想有了一定的认识,那么接下来我们分析一下这道题。
- 大问题化解成小问题,需要写一个小问题的递归方法,因此我们构造了func(ArrayList lists,int left ,int right)方法。
- 分治思想需要注意边界,这里的左边界和右边界是以链表为单位的,而不是节点。
- 我们还需要一个合并两个有序链表的方法,在上面那道题就是,我们可以直接复制过来。
2.4 代码展示与分析
下面是合并k个有序链表的代码,我会通过注释带大家简单分析一下。
public class Solution {public ListNode mergeKLists(ArrayList<ListNode> lists) {//需要返回一个节点//传参func,参数为集合lists,左边界0和右边界lists.size()-1return func(lists,0,lists.size()-1);}//下面是一个递归方法//也就是大问题化解为小问题的过程private ListNode func(ArrayList<ListNode> lists,int left ,int right){//左边界大于右边界的时候化解结束if(left > right){return null;//左边界等于右边界的时候,返回该节点//因为这里左右节点的下标相同//所以写lists.get(left)或者lists.get(right)都行} else if(left == right){return lists.get(left);//left < right的时候,就要再次进行划分//因为咱们只有合并两个链表的方法} else{int mid = (left + right) / 2;return merge(func(lists,left,mid),func(lists,mid+1,right));}}//下面的方法就是第一道题的答案,就不做详细说明了private ListNode merge(ListNode list1,ListNode list2){ListNode newHead = new ListNode(-1);ListNode cur = newHead;while(list1 != null && list2 != null){if(list1.val < list2.val){cur.next = list1;cur = cur.next;list1 = list1.next;} else {cur.next = list2;cur = cur.next;list2 = list2.next;}}if(list1 == null){cur.next = list2;} else {cur.next = list1;}return newHead.next;}
}
后序:
我相信大家通过这两道题学到了很多,第一道题比较简单,但大家不要眼高手低,还是多加练习,熟能生巧,第二道题需要掌握分治思想,可能大家一看到递归就会头疼,代码不多,但是却不容易理解,这个东西需要多加练习,琢磨,画图,需要自己不断去品味,去感受,不要畏惧,做的多了,你会感到所谓的递归其实没有那么难。哈哈,今天的内容到这里也就结束了,希望小小的我能够帮助到大家。💞💞💞
相关文章:

【Day6】合并两个排序链表与合并k个已排序的链表,java代码实现
前言: 大家好,我是良辰丫🚀🚀🚀,今天与大家一起做两道牛客网的链表题,好久写关于链表题的博客了,这两道题可以帮大家巩固一下链表知识,我把两道题的链接放到下面…...
Swagger PHP
PHP使用Swagger生成好看的API文档不是不可能,而是非常简单。首先本人使用Laravel框架,所以在Laravel上安装swagger-php。一、安装swagger - phpcomposer require zircote/swagger-phpswagger-php提供了命令行工具,所以可以全局安装࿰…...
谷粒商城-品牌管理-JSR303数据校验
后端在处理前端传过来的数据时,尽管前端表单已经加了校验逻辑,但是作为严谨考虑,在后端对接口传输的数据做校验也必不可少。 开启校验: 实体类上增加校验注解,接口参数前增加Valid 开启校验 package com.xxh.product.…...

Java零基础教程——数组
目录数组静态初始化数组数组的访问数组的动态初始化元素默认值规则:数组的遍历数组遍历-求和冒泡排序数组的逆序交换数组 数组就是用来存储一批同种类型数据的容器。 20, 10, 80, 60, 90 int[] arr {20, 10, 80, 60, 90}; //位置 0 1 2 3 4数组的…...

AirServer在哪下载?如何免费使用教程
苹果手机投屏到电脑mac是怎么弄?你知道多少?相信大家对苹果手机投屏到电脑mac能在电脑上操作不是很了解,下面就让coco玛奇朵带大家一起了解一下教程。AIrServer是一款ios投屏到mac的专用软件,可将iOS上的音频,视频&…...

加载sklearn covtype数据集出错 fetch_covtype() HTTPError: HTTP Error 403: Forbidden解决方案
大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。喜欢通过博客创作的方式对所学的知识进行总结与归纳,不仅形成深入且独到的理…...
理论六:为什么基于接口而非实现编程?有必要为每个类定义接口么?
在上一节课中、我们讲了接口和抽象类,以及各种编程语言是如何支持、实现这两个语法概念的。今天,我们继续讲一个跟“接口”相知识点:基于接口而非实现编程。这个原则非常重要,是一种非常有效的提高代码质量的手段,在平时的开发中特别经常被用到。为了让你…...
(HP)react日常开发技巧
高级特性 1,protals(传送门):将子组件渲染到父组件之外。 实例场景:父组件的儿子是<Modal>组件,使用fixed定位虽然样式看着是在父组件之外了,但是打开控制台查看元素,Modal相…...
【20230211】【剑指1】搜索与回溯算法II
树的子结构递归思维:对称性递归什么是对称性递归?就是对一个对称的数据结构(这里指二叉树)从整体的对称性思考,把大问题分解成子问题进行递归,即不是单独考虑一部分(比如树的左子树),而是同时考…...

STM32F103C8T6—库函数应用I2C/SPI驱动OLED显示中文、字符串
文章目录1. I2C与SPI通信协议对比2. 四脚OLED与六脚OLED3. I2C驱动OLED显示oled.h & oled.c:汉字取模 & oledfont.h:main.c 显示示例:连线方法:4. SPI驱动OLED显示1. I2C与SPI通信协议对比 I2C(Inter-Integra…...
sql语句要注意的地方及常用查询语句
sql要注意的地方关键字不能被缩写,也不能分行小写大写不敏感,没区别使用缩进提高语句的可读性常用查询语句1.查询所有库SHOW DATABASES;2.选择数据库 use 数据库名USE myemployees;3.查看数据库中所有表show tables4.查看表中的内容 select 字段一&#…...
数组去重、伪数组和真数组的区别以及伪数组如何转换成真数组
1.数组去重 1) 利用数组的indexOf下标属性来查询。 如果找到一个 item,则返回 item 的第一次出现的位置。开始位置的索引为 0。 如果在数组中没找到指定元素则返回 -1。 function unique4(arr) {var newArr []for (var i 0; i < arr.length; i) {i…...

JavaScript内置支持类Array
<!DOCTYPE html> <html> <head> <meta charset"utf-8"> <title>内置支持类Array</title> </head> <body bgcolor"antiquewhite"> <script type"text/javasc…...

GitLab CI-CD 学习笔记
概述 1. CI/CD CI(持续集成)指开发人员一天内进行多次合并和提交代码操作,并通过自动化测试,完成构建 CD(持续部署)指每次代码更改都会自动部署到对应环境 CI/CD 结合在一起,可以加快开发团…...

K8S安装
1.创建三台centos虚拟机 使用的官方最小镜像安装 CentOS-7-x86_64-Minimal-1804.iso 建议最小硬件配置:2核CPU、2G内存、20G硬盘 master配置详情 node1和node2配置详情 三台虚拟机在安装centos的时候在网络IPV4指定DHCP,配置IPV4固定地址,保证可以访问…...

【C++】模板初阶STL简介
今天,你内卷了吗? 文章目录一、泛型编程二、函数模板(显示实例化和隐式实例化)1.函数模板格式2.单参数模板3.多参数模板4.模板参数的匹配原则三、类模板(没有推演的时机,统一显示实例化)1.类模…...

备战蓝桥杯第一天【二分查找无bug版】
🌹作者:云小逸 📝个人主页:云小逸的主页 📝Github:云小逸的Github 🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前…...

Java集合中的Map
MapMap接口键 值 对存储键不能重复,值可以重复Map三个实现类的存储结构HashMap:Hash表链表红黑树结构 线程不安全TreeMap: 底层红黑树实现HashTable:hash表链表红黑树 线程安全HashMapHashMap常用方法HashMap<String,String>…...
【java】springboot项目启动数据加载内存中的三种方法
文章目录一、前言二、加载方式2.1、 第一种:使用PostConstruct注解(properties/yaml文件)。2.2、 第二种:使用Order注解和CommandLineRunner接口。2.3、 第三种:使用Order注解和ApplicationRunner接口。三、代码示例3.…...

【GO】29.go-gin支持ssl/tls,即https示例
本文为演示采用自签名证书一.生成证书通过openssl工具生成证书1.1 安装opensslmacos通过brew安装brew install openssl1.2 生成跟证书私钥openssl genrsa -out ca.key 40961.3 准备配置文件vim ca.conf内容如下[ req ] default_bits 4096 distinguished_name req_disti…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...

windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...

20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题
20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题 2025/6/9 20:54 缘起,为了跨网段推流,千辛万苦配置好了网络参数。 但是命令iptables -t filter -F tetherctrl_FORWARD可以在调试串口/DEBUG口正确执行。…...