Java 实现合并两个有序链表:递归与迭代
Java 实现合并两个有序链表:递归与迭代
在面试和算法题中,合并两个有序链表是一个经典问题。通过这个问题,不仅可以考察候选人的基础数据结构掌握情况,还能测试他们对递归和迭代等编程技巧的应用能力。
本文将讨论如何使用 Java 递归与迭代两种方法来实现合并两个有序链表。
问题描述
给定两个有序链表 list1 和 list2,将它们合并成一个新的有序链表,并返回合并后的链表。
示例:
- 输入:
list1 = [1,2,4],list2 = [1,3,4] - 输出:
[1,1,2,3,4,4]
方法一:递归实现
递归是一种非常直观且简洁的方法,特别适用于类似链表这种天然递归的数据结构。下面是基于递归的解决方案:
public class MergeTwoSortedList {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 如果list1为空,则直接返回list2if(list1 == null) return list2;// 如果list2为空,则直接返回list1if (list2 == null) return list1;// 如果list1的值小于list2的值if (list1.val < list2.val) {// 递归调用mergeTwoLists函数,将list1的下一个节点和list2进行合并,并将结果赋值给list1的nextlist1.next = mergeTwoLists(list1.next, list2);// 返回list1return list1;} else {// 递归调用mergeTwoLists函数,将list1和list2的下一个节点进行合并,并将结果赋值给list2的nextlist2.next = mergeTwoLists(list1, list2.next);// 返回list2return list2;}}
}
递归方法的思路解析:
-
基本情况:
- 如果
list1为null,则直接返回list2,因为此时list2仍然有值,且不需要进一步操作。 - 如果
list2为null,则直接返回list1,同理。
- 如果
-
递归情况:
- 比较
list1和list2的当前节点值。如果list1的值较小,那么我们将list1.next与list2合并,并将结果赋值给list1.next,然后返回list1。 - 否则,将
list2.next与list1合并,并将结果赋值给list2.next,然后返回list2。
- 比较
-
递归结束:
- 递归的结束条件是某一个链表到达末尾,此时直接返回另一个链表剩余的部分。
方法二:迭代实现
虽然递归方法简单易懂,但在深度较大的链表上可能会导致栈溢出问题。因此,使用迭代方法更为稳健。下面是使用迭代方法实现的代码:
public class MergeTwoSortedList {public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {// 创建一个虚拟头节点,以便于操作ListNode sentinel = new ListNode(-1);ListNode prev = sentinel;// 合并两个链表,直到其中一个链表为空while (list1 != null && list2 != null) {// 如果list1的当前节点值小于list2的当前节点值if (list1.val < list2.val) {// 将list1的当前节点接到prev的后面prev.next = list1;// 移动list1的指针到下一个节点list1 = list1.next;} else {// 将list2的当前节点接到prev的后面prev.next = list2;// 移动list2的指针到下一个节点list2 = list2.next;}// 移动prev的指针到下一个节点prev = prev.next;}// 如果list1还有剩余节点,则将剩余节点接到prev的后面// 否则将list2的剩余节点接到prev的后面prev.next = list1 == null ? list2 : list1;// 返回合并后的链表的头节点return sentinel.next;}
}
迭代方法的思路解析:
-
创建哨兵节点:
- 我们使用一个哨兵节点
sentinel来简化链表头节点的处理,最终返回sentinel.next即为合并后的链表头。
- 我们使用一个哨兵节点
-
循环比较:
- 使用
prev指针遍历并合并两个链表,将较小的节点接到prev后面,并向前移动相应链表的指针。
- 使用
-
处理剩余节点:
- 当一个链表处理完后,将另一个链表的剩余部分直接接在
prev后面。
- 当一个链表处理完后,将另一个链表的剩余部分直接接在
-
返回结果:
- 最后返回
sentinel.next即为合并后的链表。
- 最后返回
测试代码
以下是一个简单的测试用例,验证我们的实现是否正确:
public static void main(String[] args) {ListNode listNode = new MergeTwoSortedList().mergeTwoLists1(new ListNode(1, new ListNode(2)), new ListNode(2, new ListNode(4)));new MergeTwoSortedList().printListNode(listNode);
}
运行结果为:1 2 2 4,表示合并操作成功。
结论
本文讨论了在 Java 中使用递归和迭代两种方式实现合并两个有序链表的方法。递归方法简洁直观,但可能会遇到栈溢出问题;而迭代方法稍微复杂一些,但更为稳健。在实际应用中,开发者可以根据具体情况选择合适的方法。
相关文章:
Java 实现合并两个有序链表:递归与迭代
Java 实现合并两个有序链表:递归与迭代 在面试和算法题中,合并两个有序链表是一个经典问题。通过这个问题,不仅可以考察候选人的基础数据结构掌握情况,还能测试他们对递归和迭代等编程技巧的应用能力。 本文将讨论如何使用 Java…...
【每日刷题】Day98
【每日刷题】Day98 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. 大数加法_牛客题霸_牛客网 (nowcoder.com) 2. 大数乘法_牛客题霸_牛客网 (nowcoder.com) 3. 扑克牌…...
51单片机-LED实验二
使用51单片机进行LED灯的实验,使用8个LED灯展示二进制数,使用独立按键控制二进制数的加法,每次按下独立按键K2,就让二进制数加一,定义了一个LedNum,表示二进制数,二进制数取反之后可以得到输出到LED端口的8…...
批发行业进销存-webview 读取NFC,会员卡 源码CyberWinApp-SAAS 本地化及未来之窗行业应用跨平台架构
一、混合应用开发 混合应用顾名思义就是网页html和原生APP共同作用的结果 好处在一既有web的跨平台优势(安卓、苹果,电脑、国产电脑、平板电脑,自助机都能用) 好处二可以离线使用,比较稳定 好处三可以与本地硬件交…...
博弈dp,CF 731E - Funny Game
一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 731E - Funny Game 二、解题报告 1、思路分析 游戏规则其实就是交替取前缀和 考虑 f(i) 为 某人先手取前 i 个,最终能得到的最大分差 由于每人都是最佳发挥,所以有如下状态转移&am…...
基础知识:深入理解MongoDB、MySQL与Redis的应用与实践
基础知识:深入理解MongoDB、MySQL与Redis的应用与实践 在现代应用开发中,数据库系统的选择对于系统的性能、扩展性和维护性有着至关重要的影响。MongoDB、MySQL 和 Redis 是三种流行的数据库技术,它们各自有着独特的特点和适用场景。本文将详…...
Reids中List类型、Set类型、SortedSet类型的常用指令
List类型: Redis中的List类型与Java中的LinkedList类似,可以看做是一个双向链表结构。既可以支持正向检索和也可以支持反向检索。 特征也与LinkedList类似: 有序元素可以重复插入和删除快查询速度一般 常用来存储一个有序数据,…...
K8S Ingress 常用配置
目录 介绍ingress 安装 基本使用请查看域名重定向前后端分离配置默认证书配置指定证书配置白名单配置黑名单配置Annotations 配置ConfigMap 配置 匹配请求头速率限制限制客户端的最大连接数限制每秒钟段并发连接数限制每分钟段并发请求突发访问限制限制传输速度速率限制白名单 …...
【K8S】K8S架构及相关组件
文章目录 1 K8S总体架构2 相关组件2.1 控制面板组件2.2 节点组件2.3 附加组件 写在最后 1 K8S总体架构 K8S,全称Kubernetes,是一个开源的容器部署和管理平台,由Google开发,后捐献给云原生计算基金会(CNCF)…...
【MATLAB第108期】基于MATLAB的fast、vbsa、dynia、eet、glue、pawn、rsa敏感性分析模型合集(无目标函数)【更新中】
【MATLAB第108期】基于MATLAB的fast、vbsa、dynia、eet、glue、pawn、rsa敏感性分析模型合集(无目标函数)【更新中】 一、FAST(Fourier Amplitude Sensitivity Test) FAST(Fourier Amplitude Sensitivity Test&#…...
【K8S】为什么需要Kubernetes?
文章目录 1 什么是Kubernetes?2 三种常见的应用部署方式2.1 传统部署2.2 虚拟化部署2.3 容器化部署 3 Kubernetes的特点写在最后 1 什么是Kubernetes? Kubernetes是 一个开源的,用于管理云平台中多个主机上的容器化应用,Kubernet…...
【Linux】Linux中查找字符串中的命令
在Linux中,查找字符串的命令通常使用grep。grep是一个强大的工具,用于在文件中搜索指定模式的字符串。以下是一些基本用法: 1.在文件中查找字符串 grep "字符串" 文件名例如,查找文件example.txt中包含“hello”的行&…...
最新HTML设计搜索表单
设计搜索表单 页眉中包含表单,表单中只需包含label和Input. 实现如下效果:文本框动态变宽效果 代码:6.2.4.设计搜索表单.html <!DOCTYPE html> <html><head><meta charset"utf-8"><title></t…...
JavaScript constructor原型原型继承
constructor 在 JavaScript 中,构造函数是一种特殊的函数,使用 new 关键字来调用,用于创建对象实例。JavaScript 中的构造函数通常通过 function 关键字定义。 例如: function Person(name, age) {this.name name;this.age a…...
使用Python+moviepy保存截取视频画面
一、 使用VideoFileClip对象的的save_frame函数保存截取的第1帧画面 from moviepy.editor import * mvVideoFileClip(/home/Download/leaves.mp4) mv.save_frame(/home/Download/fst.jpg) # 默认保存截取的第1帧画面 二、 使用VideoFileClip对象的的save_frame函数保存截…...
【DOCKER】显示带UI的软件
1. Linux 1.1 宿主机开放X server权限 xhost 1.2 启动容器 docker run -it --rm --privilegedtrue --useru20 --workdir/home/u20 \ -e DISPLAYhost.docker.internal:0 u20:dev1.3 测试 # 安装测试软件 sudo apt-get -y install x11-apps# 显示测试程序 xclock2. Windows …...
Atcoder Beginner Contest 366
传送门 A - Election 2 时间限制:2秒 内存限制:1024MB 分数:100分 问题描述 在 AtCoder 市举行市长选举。候选人是 Takahashi 和 Aoki。 目前有 N 张有效选票投给了这两个候选人,并且计票正在进行中。这里࿰…...
【hexo博客问题】
windows下使用gitbash即可使用 其他bash会产生权限问题 npm install失败 $ npm install npm error code ENOENT npm error syscall open npm error path F:\pf_project\blog_pf\package.json npm error errno -4058 npm error enoent Could not read package.json: Error: E…...
用数组模拟栈和队列
栈 先进后出 //stk 表示定义的栈 //tt表示栈顶的下标 int stk[N], tt 0;//在栈顶上加入一个新的元素 stk[ tt] x;//弹出 tt --;//判断栈是否为空 if (tt > 0) 不为空 else empty//取出栈顶 stk[tt];1.题目 给定一个长度为 N 的整数数列,输出每个数左边第一个…...
Django内置后端和自定义后端
【图书介绍】《Django 5企业级Web应用开发实战(视频教学版)》_django 5企业级web应用开发实战(视频教学版)-CSDN博客 《Django 5企业级Web应用开发实战(视频教学版)》(王金柱)【摘要 书评 试读】- 京东图书 (jd.com) 5.2.3 内置…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...
用鸿蒙HarmonyOS5实现中国象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...
