剑指offer JZ16：合并两个排序的链表（伪头节点，清晰图解）_l1.vall java-程序员宅基地
技术标签： 算法 java 链表 新星计划 # 剑指offer 数据结构
解题思路：
- 根据题目描述， 链表 l1、l2是 递增 的，因此容易想到使用双指针l1、l2遍历两链表，根据l1.val、l2.val 的大小关系确定节点添加顺序，两节点指针交替前进，直至遍历完毕。
- 引入伪头节点： 由于初始状态合并链表中无节点，因此循环第一轮时无法将节点添加到合并链表中。解决方案：初始化一个辅助节点 dum 作为合并链表的伪头节点，将各节点添加至 dum 之后。
算法流程：
1.初始化： 伪头节点 dum ，节点 cur 指向 dum 。
2.循环合并： 当l1、l2为空时跳出；
-
当 l_1.val <= l_2.vall 时： cur的后继节点指定为 l1，并l1向前走一步；
-
当 l_1.val >= l_2.vall 时： cur的后继节点指定为 l2，并l2 向前走一步 ；
-
节点 curcur 向前走一步，即 cur = cur.next。
3.合并剩余尾部： 跳出时有两种情况，即l1 为空 或l2为空。
- 若 ll1不等于null ： 将l1添加至节点 cur 之后；
- 否则： 将l2添加至节点 curcur 之后。
4.返回值： 合并链表在伪头节点 dum 之后，因此返回 dum.next 即可。
过程图解
复杂度分析：
- 时间复杂度 O(M+N )： M,N 分别为链表 ;1 l2 的长度，合并操作需遍历两链表。
- 空间复杂度 O(1) ： 节点引用 dum , cur 使用常数大小的额外空间。
代码：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dum = new ListNode(0),cur = dum;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1==null ? l2 : l1;
return dum.next;
}
}
智能推荐
高德地图 只显示某个地区或省份，并设定显示范围_高德地图只显示某个地区-程序员宅基地
文章浏览阅读1.4w次，点赞4次，收藏30次。高德地图 只显示某个地区或省份，并设定显示范围_高德地图只显示某个地区
自动化与智能化并行：数字化运维体系助力企业腾飞-程序员宅基地
文章浏览阅读5.4k次，点赞154次，收藏120次。*《数字化运维：IT运维架构的数字化转型》**以传统运维管理体系（PPTR）为基座，在融合数字化转型、ITIL4、DevOps、SRE以及敏捷精益思想的基础上，首先提出了数字化运维管理体系 OPDM（Operation Process Data Measurement，平台化工具、高速化流程、数据化驱动、体系化度量），然后详细讲解了数字化运维一体化平台的建设路径和方法。在数字化转型的过程中，构建数字化运维体系显得尤为重要，它不仅是企业信息化建设的基石，更是推动企业数字化转型走向深入的关键环节。
转载：十款主流科研绘图软件-程序员宅基地
文章浏览阅读6.4k次，点赞2次，收藏15次。2_科研绘图软件
关于rk3588s使用facenet-pytorch-main进行onnx的转换以及RKNN生成操作_reducel2-程序员宅基地
文章浏览阅读2k次，点赞2次，收藏13次。关于rk3588s使用facenet-pytorch-main进行onnx的转换以及RKNN生成操作_reducel2
aar打包依赖 android_android中怎么把module打包成aar文件，以及怎么使用？-程序员宅基地
文章浏览阅读467次。何为aar包？jar与aar的简单区别：*.jar：只包含了class文件与清单文件 ，不包含资源文件，如图片等所有res中的文件。*.aar：包含所有资源 ，class 以及 res 资源文件全部包含一、在android studio中新建moudle1、新建module或者导入：file->new->import->new module/import module新..._android 模块化开发打包成aar再调用
django 查询条件 正则查找regex 200316_django正则查询-程序员宅基地
文章浏览阅读393次。正则查找查找正则以某开头的_django正则查询
随便推点
curl ajax 区别,Curl: RE: Curl and Ajax-程序员宅基地
文章浏览阅读172次。Date: Tue, 12 May 2009 15:48:13 +0000Hello,Thank you for quick reply.Login script ;$cookie_file_path = "/home/xxxxx/public_html/cookie.txt";$fp = fopen($cookie_file_path,'wb');fclose($fp);$agent = "Mo..._curl请求和ajx请求的区别
【QT+QGIS跨平台编译】018：【OpenSSL+Qt跨平台编译】（基于QT进行配置）_qgis ssl模式-程序员宅基地
文章浏览阅读598次，点赞14次，收藏4次。通过一套OpenSSL代码和框架，实现OpenSSL跨平台编译。在Qt环境下，集成OpenSSL库的头文件、库文件，构建跨平台编译的pro文件。通过构建的一套配置工程，基于Qt Creator IDE，完成跨平台编译实践。在Windows、Linux、MacOS等操作系统上进行测试，成功编译，形成的成果（头文件、库文件等）可在不同系统下调用或使用，从而更好地构建跨平台解决方案。采用的是OpenSSL 1.1版本。读者可参考博客中的集成原理和pro文件，构建不同版本的OpenSSL跨平台包。_qgis ssl模式
Oracle 官方Java Jdk1.8_API帮助文档+Android 开发帮助文档(中英文版）_oracle官网下载的jdkapi没中文的吗-程序员宅基地
文章浏览阅读1.6k次。Oracle 官方 Java JDK1.8_API 帮助文档（英文）JDK 1.8 API 谷歌翻译版 密码:yupnAndroid API 开发文档 （中文版）密码:nhc4Windows系统下阅读CHM:参考 百度经验Mac 阅读CHM格式的文档推荐:CHM Read App Store有下载出现乱码：解决方案：显示-文档编码-Unicode(UTF-8) ..._oracle官网下载的jdkapi没中文的吗
[一天一项目]统计元音字母_用switch语句编写程序,统计输入的一串字母中元音字母(a,e,i,o,u)的总个数和每个元-程序员宅基地
文章浏览阅读1.2k次。统计元音字母——输入一个字符串，统计处其中元音字母的数量。更复杂点的话统计出每个元音字母的数量。统计元音字母，其实和拉丁猪文字游戏有异曲同工之妙，算法其实差不多，但是统计元音字母有两种理解方式：计算总的元音字母出现次数计算每个元音字母出现的次数下面列出两种解决方法。//如果不需要具体区分每个元音字母出现的次数 private static void count(String conte_用switch语句编写程序,统计输入的一串字母中元音字母(a,e,i,o,u)的总个数和每个元
实验7-1-7 查找整数 (10分)_【id:412】【11分】g. 实验7-1-7 查找整数 (10 分) 题目描述 本题要求从输入的n-程序员宅基地
文章浏览阅读2.7k次，点赞3次，收藏2次。本题要求从输入的N个整数中查找给定的X。如果找到，输出X的位置（从0开始数）；如果没有找到，输出“Not Found”。输入格式：输入在第一行中给出两个正整数N（≤20）和X，第二行给出N个整数。数字均不超过长整型，其间以空格分隔。输出格式：在一行中输出X的位置，或者“Not Found”。输入样例1：5 73 5 7 1 9输出样例1：2输入样例2：5 73 5 8 1 9输出样例2：Not Found#include<stdio.h>int main(){_【id:412】【11分】g. 实验7-1-7 查找整数 (10 分) 题目描述 本题要求从输入的n个
Jetpack Compose中的副作用_disposableeffect-程序员宅基地
文章浏览阅读2.3k次，点赞4次，收藏7次。从本质上讲，副作用是任何超出函数控制和作用域的东西。副作用会使函数变得不确定，因此它们使开发人员难以推理代码。这对于React、Compose这类的声明式UI框架至关重要，因为它们都是通过函数（组件）的反复执行来渲染UI的，函数执行的时机和次数都不可控，但是函数的执行结果必须可控，因此，我们要求这些函数组件必须用纯函数实现。_disposableeffect