算法的学习笔记—合并两个排序的链表(牛客JZ25)
😀前言
在算法面试中,链表问题是经常遇到的考点之一,其中合并两个排序链表是一个非常经典的问题。本文将详细介绍如何通过递归和迭代两种方式实现两个有序链表的合并。
🏠个人主页:尘觉主页
文章目录
- 😀合并两个排序的链表
- 😉题目描述
- 示例1
- 示例2
- 示例3
- 🤔解题思路
- 🥰递归解法
- 递归解法的分析
- 🥰迭代解法
- 迭代解法的分析
- 😄总结
😀合并两个排序的链表
NowCoder
😉题目描述
输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围: 0≤n≤1000,−1000≤节点值≤1000
要求:空间复杂度 O(1),时间复杂度 O(n)
如输入{1,3,5},{2,4,6}时,合并后的链表为{1,2,3,4,5,6},所以对应的输出为{1,2,3,4,5,6},转换过程如下图所示:
或输入{-1,2,4},{1,3,4}时,合并后的链表为{-1,1,2,3,4,4},所以对应的输出为{-1,1,2,3,4,4},转换过程如下图所示:
示例1
- 输入:
{1,3,5}
和{2,4,6}
- 输出:
{1,2,3,4,5,6}
示例2
- 输入:
{}
和{}
- 输出:
{}
示例3
- 输入:
{-1,2,4}
和{1,3,4}
- 输出:
{-1,1,2,3,4,4}
🤔解题思路
要实现两个排序链表的合并,可以使用递归和迭代两种方法。下面分别详细讲解这两种方法的实现思路和代码。
🥰递归解法
递归解法的核心思想是比较两个链表的头节点值,并通过递归调用合并剩余部分的链表。具体而言:
- 如果
list1
的头节点值小于等于list2
的头节点值,则list1
的头节点应成为新链表的头节点,并递归合并list1
的剩余部分和list2
。 - 反之,则
list2
的头节点成为新链表的头节点,并递归合并list1
和list2
的剩余部分。
递归解法的代码实现如下:
public ListNode Merge(ListNode list1, ListNode list2) {if (list1 == null)return list2;if (list2 == null)return list1;if (list1.val <= list2.val) {list1.next = Merge(list1.next, list2);return list1;} else {list2.next = Merge(list1, list2.next);return list2;}
}
递归解法的分析
- 时间复杂度:
O(n)
。每次递归都会遍历一个节点,最终遍历完所有节点,因此时间复杂度为O(n)
。 - 空间复杂度:
O(n)
。由于递归调用占用了系统栈空间,递归深度为n
,空间复杂度为O(n)
,不满足题目对O(1)
空间复杂度的要求。
虽然递归解法简单直观,但在处理深度较大的链表时,可能会出现栈溢出的风险,因此在实际应用中通常更倾向于使用迭代解法。
🥰迭代解法
迭代解法通过维护一个指针逐步遍历两个链表,并根据节点值的大小将节点连接到新链表的末尾。具体实现步骤如下:
- 创建一个虚拟头节点
head
,用于存储合并后的链表。 - 使用
cur
指针遍历list1
和list2
,将较小值的节点链接到cur
后面,然后移动cur
和相应链表的指针。 - 如果一个链表遍历完了,直接将另一个链表剩余部分链接到
cur
后面。 - 最后返回
head.next
,即合并后的链表的头节点。
迭代解法的代码实现如下:
public ListNode Merge(ListNode list1, ListNode list2) {ListNode head = new ListNode(-1);ListNode cur = head;while (list1 != null && list2 != null) {if (list1.val <= list2.val) {cur.next = list1;list1 = list1.next;} else {cur.next = list2;list2 = list2.next;}cur = cur.next;}if (list1 != null)cur.next = list1;if (list2 != null)cur.next = list2;return head.next;
}
迭代解法的分析
- 时间复杂度:
O(n)
。同样,迭代过程中会遍历所有节点,因此时间复杂度为O(n)
。 - 空间复杂度:
O(1)
。只使用了常量级别的额外空间,满足题目对O(1)
空间复杂度的要求。
迭代解法不仅在时间和空间复杂度上更加符合题目的要求,还避免了递归深度过大的问题,因此在实际开发中更为常用。
😄总结
合并两个排序链表问题通过递归和迭代两种方法均可以有效解决。递归解法简单直观,但在空间复杂度上有所不足;迭代解法在时间和空间效率上更为优越,是实际应用中的首选方案。
希望通过本文的详细讲解,大家能够掌握这两种合并排序链表的技巧,并在算法面试或实际开发中灵活运用。
😁热门专栏推荐
想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集
linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
🤔欢迎大家加入我的社区 尘觉社区
文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞
相关文章:

算法的学习笔记—合并两个排序的链表(牛客JZ25)
😀前言 在算法面试中,链表问题是经常遇到的考点之一,其中合并两个排序链表是一个非常经典的问题。本文将详细介绍如何通过递归和迭代两种方式实现两个有序链表的合并。 🏠个人主页:尘觉主页 文章目录 😀合并…...

《虚拟之旅:开启无限可能的机器世界》简介:
1.Ubonto的介绍: Ubuntu 是一个流行的开源操作系统,基于 Linux 内核。 它具有以下一些特点和优势: 开源免费:任何人都可以免费使用、修改和分发。丰富的软件库:通过软件包管理器可以方便地安装各种应用程序。良好的…...
centos7 服务器搭建
1. 查看 centos 版本 cat /etc/redhat-release CentOS Linux release 7.9.2009 (Core)2 .查看 ip地址 ip addr sudo yum install net-tools -y 3. 是否能够上网 ping www.baidu.com ping 114.114.114.114 sudo systemctl restart network 4. DNS 更新DNS配置 编辑/etc/r…...

【Godot4自学手册】第四十五节用着色器(shader)制作水中效果
本节内容,主要学习利用着色器制作水波纹效果,效果如下: 一、搭建新的场景 首先我们新建场景,根节点选择Node2D,命名为Water,给根节点添加两个Tilemap节点,一个命名为Background主要用于绘制地…...

VMware Workstation Pro 安装 Ubuntu Server
这里写目录标题 VMware Workstation Pro 安装 Ubuntu Server1. 启动选项2. 系统语言3. 安装程序升级4. 键盘配置5. 安装类型6. 网卡配置7. 代理配置8. 系统镜像配置9. 硬盘配置10. 账户配置11. Ubuntu Pro 版本12. SSH 服务13. 推荐软件14. 安装成功15. 第一次重启报错16. 登录…...

智能化包括自动化与非自动化
智能化通常指的是系统或设备具备智能功能,以提高其自主性和效率。智能化可以分为自动化与非自动化两大类,每一类都有其独特的特点和应用场景。 一、自动化 自动化指的是系统能够在无需人为干预的情况下完成任务或操作。自动化系统通常依赖于预设的规则、…...
微前端架构的容器化部署:策略、实践与优势
随着微服务架构的兴起,微前端架构也成为现代Web应用开发的热门趋势。容器化技术,以其轻量级、可移植性和易于管理的特点,成为微前端部署的理想选择。本文将详细介绍微前端架构下应用容器化部署的策略、实践步骤以及这一方法的优势。 容器化技…...

面试题(网络、js、框架)
自我介绍 您好,面试官!我叫[您的姓名],非常荣幸能有机会参加这次面试。 在过去的 3 年里,我一直专注于前端开发领域,积累了丰富的实践经验。 在 Vue.js 项目中,我能够熟练运用组件化开发模式,实…...

C语言典型例题40
《C程序设计教程(第四版)——谭浩强》 题目 例题3.8 运输公司对用户计算运费。路程(以s表示,单位为千米),吨/千米运费越低。标准如下: s<250 没…...
【大模型部署及其应用 】使用 Ollama 和 Ollama WebUI 在本地运行 Llama 3
使用 Ollama 和 Ollama WebUI 在本地运行 Llama 3 目录 开始使用 Llama 3设置 Ollama WebUI访问 Ollama WebUI使用 Docker GenAI Stack 的 Llama 3骆驼 2 与 骆驼 3...

uniapp-部分文件中文乱码
一、问题 在开发时遇到,部分页面的中文显示乱码,如图 搜索了一下解决方法,这里记录一下 二、问题原因: 页面的编码格式不是 utf-8 造成的 三、解决方法 打开出现乱码页面选择编译器左上角的文件 > 以指定编码重新打开 选择U…...

Day41 | 647. 回文子串 516.最长回文子序列
语言 Java 647. 回文子串 回文子串 题目 给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 思路 动规五部曲来分析 1.dp数组的含义&#x…...

全面解析Gerapy分布式部署:从环境搭建到定时任务,避开Crawlab的坑
Gerapy分布式部署 搭建远程服务器的环境 装好带docker服务的系统 Docker:容器可生成镜像,也可拉去镜像生成容器 示例:将一个环境打包上传到云端(远程服务器),其他8个服务器需要这个环境直接向云端拉取镜像生成容器,进而使用该环境,比如有MYS…...

Springboot项目中使用druid实现多数据源和动态数据源,因数据库不可用导致的项目挂起的处理方案
Springboot项目中使用druid因数据库不可用导致的项目挂起的处理方案 在Spring Boot项目中使用Druid实现多数据源和动态数据源管理是一个常见的场景。通过合理的配置和错误处理机制,您可以有效地管理数据源,避免因数据库不可用而导致整个项目挂起。 1.…...
多线程 03:知识补充,静态代理与 Lambda 表达式的相关介绍,及其在多线程方面的应用
一、概述 记录时间 [2024-08-16] 前置知识:Java 基础篇;Java 面向对象 多线程 01:Java 多线程学习导航,线程简介,线程相关概念的整理 多线程 02:线程实现,创建线程的三种方式,通过多…...

机器学习中的距离概念
距离在机器学习中应用广泛,包括欧式距离、曼哈顿距离、内积距离和KL距离。 下面总结一下。 机器学习中的距离 欧式距离曼哈顿距离内积距离KL距离距离作为损失函数(MSE/MAE...)欧式距离与内积距离的联系☆距离的有效性 欧式距离 欧式距离(Euclidean Dis…...
Java 如何判断map为null或者空
1.示例一 在Java中,如果我们想判断一个Map是否为null或者空(即没有任何键值对),我们可以使用以下的方法。下面是一个完整的示例代码,展示了如何进行这样的判断: import java.util.HashMap; import java…...
终端用户视角下的性能测试,体验与度量的融合
传统的性能测试的度量标准是什么 响应时间(Response Time): 这是从客户端发出请求到接收到完整响应所需的时间。响应时间是衡量系统性能的重要指标,特别是在面向用户的应用中,因为它直接影响用户体验。 而用户体验的度…...
KCP源码解析系列(二)KCP协议结构体
一、KCP协议包 1.1 kcp协议包 kcp中只有一种数据包,不管是数据还是控制信息,都用这个数据包来表示 0 4 5 6 8 (BYTE) ---------------------------- | conv |cmd|frg| wnd | ---------------------------- 8 | …...

微软运行库全集合:一站式解决兼容性问题
开发者在部署应用程序时经常遇到因缺少运行库而引发的兼容性问题。为了解决这一问题,电脑天空推荐微软常用运行库合集,一个集成了微软多个关键运行库组件的软件包。 📚 包含组件概览: Visual Basic Virtual Machine:…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...

TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...

回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...