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

【LeetCode】剑指 Offer 25. 合并两个排序的链表 p145 -- Java Version

题目链接:https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

1. 题目介绍(25. 合并两个排序的链表)

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

【测试用例】:
示例1:
在这里插入图片描述

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

【条件约束】:

限制:

  • 0 <= 链表长度 <= 1000

【相关题目】:

注意: 本题与主站 21. 合并两个有序链表 题目相同。

2. 题解

2.1 递归(原书题解)-- O(n+m)

时间复杂度O(n+m),空间复杂度O(n+m)

就代码简单度来说,还是递归要比循环简单一些,但也要付出一些空间代价。

思想:
递归解法的思想还是十分简单的,首先主要就是对空链表的判断:

  • 当链表1为空时,那么合并链表为链表2
  • 当链表2为空时,那么合并链表为链表1
  • 当链表1和2都为空时,那么合并链表也为空

判空完毕后,开始比较头节点:

  • 当链表1头节点小于链表2头节点时,合并头节点为l1,递归寻找下一节点
  • 当链表1头节点大于链表2头节点时,合并头节点为l2,递归寻找下一节点
/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {// 判空if (l1 == null) return l2;else if (l2 == null) return l1;// 定义合并链表头节点ListNode mergeHead = null;// 合并过程// 1. 头节点比较,小的为当前节点// 2. 下一节点进入递归if (l1.val < l2.val){mergeHead = l1;mergeHead.next = mergeTwoLists(l1.next,l2);}else { mergeHead = l2;mergeHead.next = mergeTwoLists(l1,l2.next);}return mergeHead;}
}

在这里插入图片描述

2.2 循环 – O(n+m)

时间复杂度O(n+m),空间复杂度O(1)
在这里插入图片描述

引入伪头节点: 由于初始状态合并链表中无节点,因此循环第一轮时无法将节点添加到合并链表中。解决方案:初始化一个辅助节点 n1 作为合并链表的伪头节点,将各节点添加至 n1 之后,n2cur (当前节点)。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null) return list2;else if (list2 == null) return list1;ListNode n1 = new ListNode(0);ListNode n2 = n1;while (list1 != null && list2 != null){if (list1.val < list2.val){n2.next = list1;list1 = list1.next;}else{n2.next = list2;list2 = list2.next;}n2 = n2.next;}n2.next = list1 != null ? list1 : list2;return n1.next;}
}

在这里插入图片描述

3. 参考资料

[1] 面试题25. 合并两个排序的链表(伪头节点,清晰图解)-- 2.2图片来源

相关文章:

【LeetCode】剑指 Offer 25. 合并两个排序的链表 p145 -- Java Version

题目链接&#xff1a;https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/ 1. 题目介绍&#xff08;25. 合并两个排序的链表&#xff09; 输入两个递增排序的链表&#xff0c;合并这两个链表并使新链表中的节点仍然是递增排序的。 【测试用例】&#xf…...

如何应对危害机房安全的这几个常见要素?

随着现代化进程的推进&#xff0c;各行业对计算机的依赖性日益增高&#xff0c;计算机系统已经成为业务系统的重要组成部分。 在这种情况下&#xff0c;一旦机房设备出现故障&#xff0c;就会影响机房的正常运行&#xff0c;造成严重后果。尤其是银行、证券、海关等需要实时数据…...

【bug】antd全局的主题色样式被覆盖,被修改为`antd`默认的主题色

背景&#xff1a; 项目本身修改了主题色,配置如下: // umi配置文件 export default {theme: {primary-color: #2F54EB, // 全局主色}, };需要对图片上传组件做封装,并在项目中统一引用,如下 import { TdsUpload } from tdsComponents;环境信息 node tiandstiandsdeMacBook…...

MySQL DDL表操作【入门到精通】

目录 一、查询创建 1、查询当前数据库所有表 2、查看指定表结构 3、查询指定表的建表语句 4、创建表结构 二、数据类型 1、数值类型 2、字符串类型 3、日期时间类型 三、表操作-案例 设计一张员工信息表&#xff0c;要求如下&#xff1a; 对应的建表语句如下&#…...

《MySQL系列-InnoDB引擎28》表-约束详细介绍

约束 1 数据完整性 关系型数据库系统和文件系统的一个不同点是&#xff0c;关系数据库本身能保证存储数据的完整性&#xff0c;不需要应用程序的控制&#xff0c;而文件系统一般需要在程序端进行控制。当前几乎所有的关系型数据库都提供约束(constraint)机制&#xff0c;该机制…...

使用docker部署宝塔环境

经常需要部署lnmp环境&#xff0c;宝塔是一个不错的选择&#xff0c;包括安装各种插件&#xff0c;添加网站&#xff0c;设置定时任务等都非常方便。这次使用docker来部署。 拉取centos镜像 docker pull centos启动容器 1.-p端口映射&#xff0c;-d后台运行 2. 文件夹做一下映…...

ORB_SLAM2+kinect稠密建图

下载代码&#xff1a;https://github.com/gaoxiang12/ORBSLAM2_with_pointcloud_map 运行代码&#xff1a; 解压代码后&#xff0c;删掉作者自己编译的build文件夹&#xff08;下面三个都删除&#xff09;&#xff1a; ~/ORB_SLAM2_modified/build, ~/ORB_SLAM2_modified/T…...

mujoco安装及urdf转xml方法记录

参考 mujoco210及mujoco-py安装 下载适用于Linux或 OSX的 MuJoCo 2.1 版二进制文件 。 将mujoco210的下载的目录解压到~/.mujoco/mujoco210路径下. 注意&#xff1a;如果要为包指定非标准位置&#xff0c;请使用环境变量MUJOCO_PY_MUJOCO_PATH。 验证是否安装成功&#xff08…...

Visual Studio 2019 + Qt 项目版本信息新增到资源以及通过代码读取资源存储的版本信息

文章目录前言一、如何在VisualStudio2019中新增项目版本信息二、在程序中调用项目版本信息1.引入库version.lib1.1.通过vs自带的属性页引入库1.2.手动引入库2.新增版本信息读取类3.调用类获取信息总结前言 本文主要讲述如何在Visual Studio 2019 以及Qt结合的开发项目中&#…...

裸辞两个月还能不能找到工作?亲身经历告诉你结果·····

这是我在某论坛看到的一名网友的吐槽&#xff1a; 软件测试四年&#xff0c;主要是手动测试&#xff08;部分自动化测试和性能测试&#xff0c;但是用的是公司内部自动化工具&#xff0c;而且我自动化方面是弱项。&#xff09;现在裸辞两个月了&#xff0c;面试机会少而且面试…...

2023华为面试真题

【华为】面试真题&#xff1a; 面试前需要准备&#xff1a; 1. Java 八股文&#xff1a;了解常考的题型和回答思路&#xff1b; 2. 算法&#xff1a;刷 100-200 道题&#xff0c;记住刷题最重要的是要理解其思想&#xff0c;不要死记硬背&#xff0c;碰上原题很难&#xff0…...

【C++】C++11新特性——基础特性

文章目录一、列表初始化1.1 {}初始化1.2 initializer_list类型二、类型推导2.1 auto2.2 auto注意事项2.3 decltype三、新增与改进3.1 nullptr3.2 范围for3.3 array3.4 forward_list3.5 unordered系列3.6 final与override一、列表初始化 1.1 {}初始化 C11 引入了一个新的初始化…...

Mac 遇到pip: command not found问题的解决

Mac 遇到pip: command not found问题的解决在学习Playwright时候&#xff0c;需要下载相关依赖Playwright 是专门为满足端到端测试的需要而创建的。Playwright 支持所有现代渲染引擎&#xff0c;包括 Chromium、WebKit 和 Firefox。在 Windows、Linux 和 macOS 上进行本地测试或…...

[ 云计算 | Azure ] Episode 03 | 描述云计算运营中的 CapEx 与 OpEx,如何区分 CapEx 与 OpEx

正常情况如果你不是会计&#xff0c;或者对钱相关的数字比较敏感的财务&#xff0c;本文的一些东西你不会接触的&#xff0c;但是最为云架构或者云运营&#xff0c;你可能会遇到如何采购亦或者估算的我成本和运营成本等等&#xff0c;所以本文的一些知识点就需要进行一定的了解…...

STM32F103R8T6 SPWM实现正弦波输出

前言 PWM合成正弦波&#xff0c;原理什么的不详细说了&#xff0c;概括一下就是 PWM有效面积的积分 正弦波的有效面积。PWM的频率越快&#xff0c;细分的越多&#xff0c;锯齿也就越不明显。 做法是&#xff1a;首先利用正弦波取点软件&#xff0c;取点1000个&#xff0c;生…...

Oracle 11g创建和删除数据库实例

一、创建数据库实例 1.点击“开始” -> “Oracle -OraDb11g_home1” -> “Database Configuration Assistant” 2.点击“下一步” 3.选择“创建数据库”&#xff0c;点击“下一步” 4.默认设置&#xff0c;不用更改&#xff0c;直接点击“下一步” 5.填写要创建的“实例…...

MySQL(四)视图、存储过程、触发器

视图、存储过程、触发器视图检查选项视图的更新存储过程存储过程基本语法变量系统变量用户自定义变量局部变量if判断参数casewhile循环repeat循环loop循环cursor游标handler条件处理程序存储函数触发器视图 视图&#xff08;View&#xff09;是一种虚拟存在的表。视图中的数据…...

在 Ubuntu 下编写 C++

在 Ubuntu 下编写 C 在 Ubuntu 上面编写 C&#xff0c;本章节内容主要介绍在 Ubuntu 在终端窗口下使用 vi/vim 编辑一 个 C源文件。通过编写最简单的示例“Hello,World&#xff01;”。带领大家学习如何在 Ubuntu 终端下编 辑和编译 C。这里要求大家会在 Ubuntu 上使用 vi/vim…...

Linux主要目录的意思

Linux目录的意思 文章目录Linux目录的意思bin目录&#xff08;命令目录&#xff09;&#xff1a;二进制目录&#xff0c;二进制是可以直接执行的机器码&#xff0c;里面存放着可以执行的命令&#xff1b;bin目录右下角有个箭头类似于Windows的快捷方式 sbin目录&#xff1a;系…...

启动golang项目编译的exe可执行文件获取windows管理员权限(UAC)

背景&#xff1a; go代码启动以后里面涉及到修改ip地址等操作&#xff0c;需要管理员权限。打包好的exe文件双击执行默认是没有管理员权限的&#xff0c;那么修改ip就会提示需要管理员权限。 解决方法1&#xff1a;右键以管理员权限运行exe文件 解决方法2&#xff1a;编译exe…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...