Leetcode:合并两个有序链表
2024-09-01 07:20:25
class Solution {
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)。 因为每次调用递归都会去掉 l1 或者 l2 的头元素(直到至少有一个链表为空),函数 mergeTwoList 中只会遍历每个元素一次。所以,时间复杂度与合并后的链表长度为线性关系。
空间复杂度:O(n + m)。调用 mergeTwoLists 退出时 l1 和 l2 中每个元素都一定已经被遍历过了,所以 n+m 个栈帧会消耗 O(n + m) 的空间。
最新文章
- 深入理解JQuery插件开发
- js中String.prototype.format類似于.net中的string.formitz效果
- Linux ls -l内容详解
- 利用shell脚本统计文件中出现次数最多的IP
- call &;&; jmp 指令
- MongoDB入门三步曲3--部署技术:主备、副本集和数据分片
- Oracle三组难缠的hint no_unnest/unnest,push_subq,push_pred--平展化(转)
- Codeforces Round #301 (Div. 2)(A,【模拟】B,【贪心构造】C,【DFS】)
- map函数、filer函数、reduce函数的用法和区别
- python3的文件读取问题
- web项目部署到服务器中浏览器中显示乱码
- RNN生产唐诗
- C语言清空输入缓冲区的N种方法对比【转】
- MVC中使用过滤器做权限认证需要注意的地方
- HBase 第四章 HBase原理
- iOS:分段控件UISegmentedControl的详细使用
- MySQL几个join
- 《Advanced Bash-scripting Guide》学习(二):测试脚本调用的参数是否正确
- dreamweaver cs5 快捷键
- 子元素设置margin-top,父元素也受影响
热门文章
- [ubuntu][deepin]系统增加自定义开机启动项
- win10 我的电脑下面的六个文件夹的隐藏
- 一文速览Vue全栈
- 利用hash或history实现单页面路由
- WebService—— IDEA创建WebServices
- Git简易使用教程
- Ubuntu安装时出现“failed to load ldlinux.c32”
- K8S学习笔记之filebeat采集K8S微服务java堆栈多行日志
- NLP系列文章:子词嵌入(fastText)的理解!(附代码)
- 修改jdk注册表