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

LeetCode刷题---合并两个有序链表

个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏:http://t.csdnimg.cn/ZxuNL

                 http://t.csdnimg.cn/c9twt


前言:这个专栏主要讲述递归递归、搜索与回溯算法,所以下面题目主要也是这些算法做的  

我讲述题目会把讲解部分分为3个部分:
1、题目解析

2、算法原理思路讲解

3、代码实现


一、合并两个有序链表 

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目:

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

提示:

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

二、解法 

题目解析

 根据题目意思:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

说明我们不能直接去新建一个链表,我们只能直接改变旧链表的指向来合并成一个新的链表 



算法原理思路讲解 

注意:我们在做递归这一类题目是要将递归看作一个黑盒,我们不管他是如何实现的,我们就相信他一定可以帮助我们完成目标

如何去写一个递归

1、先找到相同的子问题                                   函数头的设计

2、只关心某一个子问题是如何解决的             函数体的书写

3、注意一下递归函数的出口                            终止条件   

我们可以设计一个函数头:
交给你两个链表的头结点,你帮我把它们合并起来,并且返回合并后的头结点。
ListNode* dfs(ListNode* l1, ListNode* l2)

函数体:
选择两个头结点中较⼩的结点作为最终合并后的头结点,然后将剩下的链表交给递归函数去处理。
1、比较两个链表的头结点值的大小(如果l1小
2、l1->next = dfs(l1->next,l2);
3、返回合并后的头结点,也就是l1
if (l1->val <= l2->val)
{l1->next = dfs(l1->next,l2);return l1;
}

若是l2小亦然

递归出⼝:
当某⼀个链表为空的时候,返回另外⼀个链表。
以上思路就讲解完了,大家可以先自己先做一下
大家注意:链表的题⼀定要画图,搞清楚指针的操作!

代码实现:

class Solution 
{
public:ListNode* dfs(ListNode* l1, ListNode* l2){if ( l1 == nullptr) return l2;if ( l2 == nullptr) return l1;if (l1->val <= l2->val){l1->next = dfs(l1->next,l2);return l1;}else{l2->next = dfs(l1,l2->next);return l2;}}ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {return dfs(list1,list2);}
};

相关文章:

LeetCode刷题---合并两个有序链表

个人主页&#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏&#xff1a;http://t.csdnimg.cn/ZxuNL http://t.csdnimg.cn/c9twt 前言&#xff1a;这个专栏主要讲述递归递归、搜索与回溯算法&#xff0c;所以下面题目主要也是这些算法做的 我讲述…...

SQL Server 2008 使用concat报错

SQL Server 2008 使用concat报错 在 SQL Server中&#xff0c;CONCAT 函数是从 SQL Server 2012 版本开始引入的&#xff0c;所以在 SQL Server 2008 中使用 CONCAT 函数会导致错误。 如果你想要连接字符串&#xff0c;有几种替代方法可以考虑&#xff1a; 使用 运算符&…...

视频后期效果制作工具Mocha Pro 2022 Plugins mac中文版软件介绍

Mocha Pro 2022 mac是一款专业的三维摄像机反求摩卡跟踪插件&#xff0c;同时也是一款视频后期效果制作工具&#xff0c;Mocha Pro 2022下载能够给数字媒体艺术家提供强大的、直观的和创新的追踪解决方案用简化的界面、加速的工作流程以及轻松追踪和操作镜头的强大性&#xff0…...

人工智能时代:AIGC的横空出世

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;数据结构、网络奇遇记 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 &#x1f4cb;前言一. 什么是AIGC?二. AIGC的主要特征2.1 文本生成2.2 图像生成2.3 语音生成2.4 视…...

基于ChatGPT等大模型快速爬虫提取网页内容

本文将介绍一种基于ChatGPT等大模型快速爬虫提取网页内容的方法。传统的爬虫方法需要花费较大精力分析页面的html元素&#xff0c;而这种方法只需要两步就可以完成。下面将从使用步骤、方法扩展和示例程序三部分进行介绍。RdFast智能创作机器人小程序预计本周2023-11-30之前集成…...

JavaScript WebAPI(三)(详解)

这次介绍一下webAPI中的一些知识&#xff1a; 回调函数 回调函数是指 如果将函数A做为参数传递给函数B时&#xff0c;我们称函数A为回调函数 例如&#xff1a; // 立即执行函数中传递的函数是一个回调函数 (function(){ console.log("我是回调函数") })(); // …...

LeetCode哈希表:最长连续序列

LeetCode哈希表&#xff1a;最长连续序列 题目描述 给定一个未排序的整数数组 nums &#xff0c;找出数字连续的最长序列&#xff08;不要求序列元素在原数组中连续&#xff09;的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1&#xff1a; 输入&…...

SpringBoot+redis实现接口防刷

写一个RedisService&#xff0c;实现获取Redis 的set、get、incr&#xff08;相当于计数器&#xff09; 写inferface注解类 做一个拦截器&#xff0c;因为要先于控制器判断 将拦截器注入Springboot 文章目录 目录 文章目录 前言 一、引入依赖 二、使用步骤 2.1 RedisServic…...

5G承载网和大客户承载的演进

文章目录 移动4/5G承载网联通和电信4/5G承载网M-OTN&#xff08;Metro-optimized OTN&#xff09;&#xff0c;城域型光传送网PeOTN&#xff08;packet enhanced optical transport network&#xff09;&#xff0c;分组增强型OTN板卡增强型PeOTN集中交叉型PeOTN VC-OTN&#x…...

智慧工地一体化解决方案(里程碑管理)源码

智慧工地为管理人员提供及时、高效、优质的远程管理服务&#xff0c;提升安全管理水平&#xff0c;确保施工安全提高施工质量。实现对人、机、料、法、环的全方位实时监控&#xff0c;变被动“监督”为主动“监控”。 一、建设背景 施工现场有数量多、分布广&#xff0c;总部统…...

熬夜会秃头——beta冲刺Day2

这个作业属于哪个课程2301-计算机学院-软件工程社区-CSDN社区云这个作业要求在哪里团队作业—beta冲刺事后诸葛亮-CSDN社区这个作业的目标记录beta冲刺Day2团队名称熬夜会秃头团队置顶集合随笔链接熬夜会秃头——Beta冲刺置顶随笔-CSDN社区 目录 一、团队成员会议总结 1、成员…...

【linux】信号——信号保存+信号处理

信号保存信号处理 1.信号保存1.1信号其他相关概念1.2信号在内核中的表示 2.信号处理2.1信号的捕捉流程2.2sigset_t2.3信号集操作函数2.4实操2.5捕捉信号的方法 3.可重入函数4.volatile5.SIGCHLD信号 自我名言&#xff1a;只有努力&#xff0c;才能追逐梦想&#xff0c;只有努力…...

雷军:我的程序人生路

今天有朋友发给我一篇我在20年前在BBS上写的帖子。那还是1996年&#xff0c;我们通过电话线拨号连接到西点BBS上飙帖子玩的年代。那是一个互联网混沌初开的年代&#xff0c;那是一个BBS和Email几乎主宰了全部互联网的年代&#xff0c;那是一个青春的理想和热血沸腾的年代。 我…...

Linux 磁盘分区处理

最近实施过程中遇到客户提供给我们的服务器操作系统和Docke容器环境都已经安装完成&#xff0c;但磁盘的分区没有进行整理好。磁盘总共270G&#xff0c;系统安装分配了60G&#xff0c;剩余未创建分配需要处理。由于分区情况每家不一样&#xff0c;但大致流程都是相同的&#xf…...

利用ogr2ogr从PostGIS中导出/导入Tab/Dxf/Geojson等格式数据

ogr2ogr Demo Command 先查看下当前gdal支持的全部格式&#xff0c;部分gdal版本可能不支持PostGIS。 如出现PostgreSQL表名支持。 #全部支持的格式 ogrinfo --formats | sort #AVCBin -vector- (rov): Arc/Info Binary Coverage #AVCE00 -vector- (rov): Arc/Info E00 (ASC…...

【深度优先】LeetCode1932:合并多棵二叉搜索树

作者推荐 动态规划LeetCode2552&#xff1a;优化了6版的1324模式 题目 给你 n 个 二叉搜索树的根节点 &#xff0c;存储在数组 trees 中&#xff08;下标从 0 开始&#xff09;&#xff0c;对应 n 棵不同的二叉搜索树。trees 中的每棵二叉搜索树 最多有 3 个节点 &#xff0…...

monorepo多项目管理主流实现方式:1.learn + yarn/npm workspace 2.pnpm

npm域级包 随着npm包越来越多&#xff0c;而且包名也只能是唯一的&#xff0c;如果一个名字被别人占了&#xff0c;那你就不能再使用这个名字&#xff1b;假设我想要开发一个utils包&#xff0c;但是张三已经发布了一个utils包&#xff0c;那我的包名就不能叫utils了&#xff…...

【斗罗二】暗杀霍雨浩行动,马小桃霸气回击,江楠楠首秀武魂兔兔

Hello,小伙伴们&#xff0c;我是拾荒君。 《斗罗大陆Ⅱ绝世唐门》第25集更新了&#xff01;和小伙伴们一样&#xff0c;一更新&#xff0c;拾荒君就急不可待地观看这一集。故事情节高潮迭起&#xff0c;尤其是霍雨浩与王冬面对六名杀手的惊险场景&#xff0c;真是让人心跳加速…...

[ 蓝桥杯Web真题 ]-年度明星项目

目录 引入 介绍 准备 目标 效果 规定 思路 知识补充 解答参考 引入 hello&#xff0c;大家好&#xff01;我注意到了之前发的一篇蓝桥杯Web应用开发的文章是关注度最高的&#xff0c;可能大部分关注我的小伙伴对蓝桥杯Web应用开发比较感兴趣&#xff0c;或者想要参加…...

Maven终端打包时报Unknown lifecycle phase “.test.skip=true“

错误实例代码 mvn clean package -Dmaven.test.skiptrue 再windows的cmd窗口进行项目打包&#xff0c;需要将参数用英文符号包裹起来“ ” 【正确的实例】&#xff1a;mvn clean package ’-Dmaven.test.skiptrue‘ PS D:\BaiduNetdiskDownload\qian\Springboot-Vue\bi…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...