当前位置: 首页 > news >正文

【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代码实现

前言&#xff1a; 大家好&#xff0c;我是良辰丫&#x1f680;&#x1f680;&#x1f680;&#xff0c;今天与大家一起做两道牛客网的链表题&#xff0c;好久写关于链表题的博客了&#xff0c;这两道题可以帮大家巩固一下链表知识&#xff0c;我把两道题的链接放到下面&#xf…...

Swagger PHP

PHP使用Swagger生成好看的API文档不是不可能&#xff0c;而是非常简单。首先本人使用Laravel框架&#xff0c;所以在Laravel上安装swagger-php。一、安装swagger - phpcomposer require zircote/swagger-phpswagger-php提供了命令行工具&#xff0c;所以可以全局安装&#xff0…...

谷粒商城-品牌管理-JSR303数据校验

后端在处理前端传过来的数据时&#xff0c;尽管前端表单已经加了校验逻辑&#xff0c;但是作为严谨考虑&#xff0c;在后端对接口传输的数据做校验也必不可少。 开启校验&#xff1a; 实体类上增加校验注解&#xff0c;接口参数前增加Valid 开启校验 package com.xxh.product.…...

Java零基础教程——数组

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

AirServer在哪下载?如何免费使用教程

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

加载sklearn covtype数据集出错 fetch_covtype() HTTPError: HTTP Error 403: Forbidden解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。喜欢通过博客创作的方式对所学的知识进行总结与归纳,不仅形成深入且独到的理…...

理论六:为什么基于接口而非实现编程?有必要为每个类定义接口么?

在上一节课中、我们讲了接口和抽象类&#xff0c;以及各种编程语言是如何支持、实现这两个语法概念的。今天&#xff0c;我们继续讲一个跟“接口”相知识点:基于接口而非实现编程。这个原则非常重要,是一种非常有效的提高代码质量的手段,在平时的开发中特别经常被用到。为了让你…...

(HP)react日常开发技巧

高级特性 1&#xff0c;protals&#xff08;传送门&#xff09;&#xff1a;将子组件渲染到父组件之外。 实例场景&#xff1a;父组件的儿子是<Modal>组件&#xff0c;使用fixed定位虽然样式看着是在父组件之外了&#xff0c;但是打开控制台查看元素&#xff0c;Modal相…...

【20230211】【剑指1】搜索与回溯算法II

树的子结构递归思维&#xff1a;对称性递归什么是对称性递归&#xff1f;就是对一个对称的数据结构&#xff08;这里指二叉树&#xff09;从整体的对称性思考&#xff0c;把大问题分解成子问题进行递归&#xff0c;即不是单独考虑一部分(比如树的左子树)&#xff0c;而是同时考…...

STM32F103C8T6—库函数应用I2C/SPI驱动OLED显示中文、字符串

文章目录1. I2C与SPI通信协议对比2. 四脚OLED与六脚OLED3. I2C驱动OLED显示oled.h & oled.c&#xff1a;汉字取模 & oledfont.h&#xff1a;main.c 显示示例&#xff1a;连线方法&#xff1a;4. SPI驱动OLED显示1. I2C与SPI通信协议对比 I2C&#xff08;Inter-Integra…...

sql语句要注意的地方及常用查询语句

sql要注意的地方关键字不能被缩写&#xff0c;也不能分行小写大写不敏感&#xff0c;没区别使用缩进提高语句的可读性常用查询语句1.查询所有库SHOW DATABASES;2.选择数据库 use 数据库名USE myemployees;3.查看数据库中所有表show tables4.查看表中的内容 select 字段一&#…...

数组去重、伪数组和真数组的区别以及伪数组如何转换成真数组

1.数组去重 1&#xff09; 利用数组的indexOf下标属性来查询。 如果找到一个 item&#xff0c;则返回 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&#xff08;持续集成&#xff09;指开发人员一天内进行多次合并和提交代码操作&#xff0c;并通过自动化测试&#xff0c;完成构建 CD&#xff08;持续部署&#xff09;指每次代码更改都会自动部署到对应环境 CI/CD 结合在一起&#xff0c;可以加快开发团…...

K8S安装

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

【C++】模板初阶STL简介

今天&#xff0c;你内卷了吗&#xff1f; 文章目录一、泛型编程二、函数模板&#xff08;显示实例化和隐式实例化&#xff09;1.函数模板格式2.单参数模板3.多参数模板4.模板参数的匹配原则三、类模板&#xff08;没有推演的时机&#xff0c;统一显示实例化&#xff09;1.类模…...

备战蓝桥杯第一天【二分查找无bug版】

&#x1f339;作者:云小逸 &#x1f4dd;个人主页:云小逸的主页 &#x1f4dd;Github:云小逸的Github &#x1f91f;motto:要敢于一个人默默的面对自己&#xff0c;强大自己才是核心。不要等到什么都没有了&#xff0c;才下定决心去做。种一颗树&#xff0c;最好的时间是十年前…...

Java集合中的Map

MapMap接口键 值 对存储键不能重复&#xff0c;值可以重复Map三个实现类的存储结构HashMap&#xff1a;Hash表链表红黑树结构 线程不安全TreeMap&#xff1a; 底层红黑树实现HashTable&#xff1a;hash表链表红黑树 线程安全HashMapHashMap常用方法HashMap<String,String>…...

【java】springboot项目启动数据加载内存中的三种方法

文章目录一、前言二、加载方式2.1、 第一种&#xff1a;使用PostConstruct注解&#xff08;properties/yaml文件&#xff09;。2.2、 第二种&#xff1a;使用Order注解和CommandLineRunner接口。2.3、 第三种&#xff1a;使用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…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...