当前位置:网站首页>LeetCode热题(11.合并两个有序链表)
LeetCode热题(11.合并两个有序链表)
2022-08-09 11:42:00 【识时务者-HJJ】
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 均按 非递减顺序 排列
package com.leetcode;
import java.util.ArrayList;
import java.util.List;
/** * @Author Handsome * @Date 2022/8/9 10:12 * @Version 1.0 */
public class 合并两个有序链表 {
/** * Definition for singly-linked list. */
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 static void main(String[] args) {
ListNode listNode = mergeTwoLists(
new ListNode(1,
new ListNode(2,
new ListNode(4))),
new ListNode(1,
new ListNode(3,
new ListNode(4))));
List list = new ArrayList();
while (listNode != null) {
list.add(listNode.val);
listNode = listNode.next;
}
System.out.println(list);
// 输入 [1,2,4] [1,3,4]
// 输出 [1,1,2,3,4,4]
}
/** * 复杂度分析: * 时间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。 * 因为每次调用递归都会去掉 l1 或者 l2 的头节点(直到至少有一个链表为空), * 函数 mergeTwoList 至多只会递归调用每个节点一次。 * 因此,时间复杂度取决于合并后的链表长度,即 O(n+m)。 * 空间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。 * 递归调用 mergeTwoLists 函数时需要消耗栈空间,栈空间的大小取决于递归调用的深度。 * 结束递归调用时 mergeTwoLists 函数最多调用 n+m 次,因此空间复杂度为 O(n+m)。 */
public static 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;
}
}
}
我的学习论坛
HandsomeForum:用Java编写的学习论坛,打造我们自己的圈子!(http://huangjunjie.vip:66)
边栏推荐
猜你喜欢
随机推荐
《数字经济全景白皮书》银行业智能营销应用专题分析 发布
win10 outlook邮件设置
mysql + redis + flask + flask-sqlalchemy + flask-session 配置及项目打包移植部署
在北京参加UI设计培训到底怎么样?
实验记录:搭建网络过程
PAT1006
Web console control edit box
MySQL执行sql语句的机制
修改VOT2018.json文件,去掉图片路径中的color
_main C:/ti/ccs1011/ccs/tools/compiler/ti-cgt-c2000_20.2.1.LTS/lib/rts2800_fpu32.lib<ar在线升级跳转疑问
Visual Studio 2017 ASP.NET Framework MVC 项目 MySQL 配置连接
Paper Sharing | ACL2022 | Argument Relation Extraction Based on Transfer Learning
【Basic model】Transformer-实现中英翻译
WPF implements a MessageBox message prompt box with a mask
MySQL中的锁
LeetCode 1413.逐步求和得到正数的最小值
Redis的常用数据结构和底层实现方式
Notepad++安装插件
bat文件(批处理文件)运行时一闪而过解决方法
学生成绩查找系统