当前位置: 首页 > 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…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...