题目出处
题目描述

个人解法
思路:
todo
代码示例:(Java)
todo
复杂度分析
todo
官方解法
方法1:递归
思路:

代码示例:(Java)
@Data
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
复杂度分析
- 时间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点(直到至少有一个链表为空),函数 mergeTwoList 至多只会递归调用每个节点一次。因此,时间复杂度取决于合并后的链表长度,即 O(n+m)。
- 空间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间,栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次,因此空间复杂度为 O(n+m)。
方法2:迭代
思路:


代码示例:(Java)
@Data
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
复杂度分析
- 时间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中,l1 和 l2 只有一个元素会被放进合并链表中, 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的,因此总的时间复杂度为 O(n+m)。
- 空间复杂度:O(1)。我们只需要常数的空间存放若干变量。
考察知识点
1.Java基本类型的默认值
收获
1.如何构建一个空链表
2.递归与迭代
3.多张图片转为gif动图
实战链接 完全免费
4.如何快速保存一个网站页面的一些代码和图片
1)打开网页,ctrl+s
2)以https://leetcode.cn/problems/merge-two-sorted-lists/solutions/226408/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/页面为例,保存后生成的文件如下:

文件中相关的代码和图片

Gitee源码位置
同名文章,已同步发表于CSDN,个人网站,公众号
FEATURED TAGS
Cursor
AI
蝇量模式
责任链模式
工厂设计模式
观察者设计模式
每日一个设计模式
Spring中的设计模式
策略设计模式
设计模式原则
设计模式分类
Redis数据类型及应用
分布式锁
spring循环依赖
SpringAop
工一影单
书单
AQS
LockSupport
两数之和
字节跳动
leetcode
58同城
经典书籍
深入理解Java虚拟机
OpenJDK
Java基础
GitHub的骚操作
彩蛋
JDK
JVM性能分析工具
JVM监控
CPU占用过高解决思路
Linux常用命令
线上故障分析
G1垃圾收集器
垃圾收集器生产配置
默认的垃圾收集器
垃圾收集器
GC垃圾回收算法
OOM
虚引用
弱引用
软引用
强引用
Java的四大引用
jvm常用基本配置参数
JVM参数配置
JVM系统默认值
JVM调优
GC Roots
JVM垃圾回收
常见的垃圾回收算法
GC的作用域
JVM内存结构
ThreadPoolExecutor
线程池
阻塞队列
Semaphore
CyclicBarrier
CountDownLatch
自旋锁
Java锁
线程安全
ArrayList
原子更新
原子引用
ABA
AtomicInteger
CAS
高并发
多线程
juc
数据库连接工具
程序员简历
activeMQ
异步
消息队列
购物车
京东
分布式系统
单点登陆
集群
zookeeper
搜素引擎
solr
es
IO
数据结构
Redis
算法
GC
JVM
索引
MySQL
Redis持久化
git
Centos
服务类命令
Linux
字段不一致
MyBatis
工作流程
原理
post请求乱码
SpringMVC
传播属性
隔离级别
数据库事务
笔记
大数据
前端
Java
Bean作用域
Spring
JavaEE
Java变量
循环迭代
递归
循环与迭代
方法参数传递
类的实例化
类的初始化
设计模式
自增变量
面试题
JavaSE
安装教程
教程
