力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
面试题 17.12. BiNode
0001. 两数之和
0020. 有效的括号
0021. 合并两个有序链表
0026. 删除排序数组中的重复项
0053. 最大子序和
0160. 相交链表
0066. 加一
0088. 合并两个有序数组
0101. 对称二叉树
0104. 二叉树的最大深度
0108. 将有序数组转换为二叉搜索树
0121. 买卖股票的最佳时机
0122. 买卖股票的最佳时机 II
0125. 验证回文串
0136. 只出现一次的数字
0155. 最小栈
0167. 两数之和 II 输入有序数组
0169. 多数元素
0172. 阶乘后的零
0190. 颠倒二进制位
0191. 位 1 的个数
0198. 打家劫舍
0203. 移除链表元素
0206. 反转链表
0219. 存在重复元素 II
0226. 翻转二叉树
0232. 用栈实现队列
0263. 丑数
0283. 移动零
0342. 4 的幂
0349. 两个数组的交集
0371. 两整数之和
401. 二进制手表
0437. 路径总和 III
0455. 分发饼干
0504. 七进制数
0575. 分糖果
0665. 非递减数列
0661. 图片平滑器
821. 字符的最短距离
0874. 模拟行走机器人
1128. 等价多米诺骨牌对的数量
1260. 二维网格迁移
1332. 删除回文子序列
第五章 - 高频考题(中等)
第六章 - 高频考题(困难)
后序
由
GitBook
提供支持
0021. 合并两个有序链表
题目地址(21. 合并两个有序链表)
https://leetcode-cn.com/problems/merge-two-sorted-lists
题目描述
1
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
2
3
示例:
4
5
输入:1->2->4, 1->3->4
6
输出:1->1->2->3->4->4
Copied!
前置知识
递归
链表
公司
阿里
字节
腾讯
amazon
apple
linkedin
microsoft
公司
阿里、字节、腾讯
思路
本题可以使用递归来解,将两个链表头部较小的一个与剩下的元素合并,并返回排好序的链表头,当两条链表中的一条为空时终止递归。
关键点
掌握链表数据结构
考虑边界情况
代码
语言支持:CPP, JS
CPP Code:
1
class
Solution
{
2
public
:
3
ListNode
*
mergeTwoLists
(
ListNode
*
l1
,
ListNode
*
l2
)
{
4
if
(
l1
==
nullptr
)
{
5
return
l2
;
6
}
else
if
(
l2
==
nullptr
)
{
7
return
l1
;
8
}
else
if
(
l1
->
val
<
l2
->
val
)
{
9
l1
->
next
=
mergeTwoLists
(
l1
->
next
,
l2
);
10
return
l1
;
11
}
else
{
12
l2
->
next
=
mergeTwoLists
(
l1
,
l2
->
next
);
13
return
l2
;
14
}
15
}
16
};
Copied!
JS Code:
1
/**
2
* Definition for singly-linked list.
3
* function ListNode(val) {
4
* this.val = val;
5
* this.next = null;
6
* }
7
*/
8
/**
9
* @param {ListNode} l1
10
* @param {ListNode} l2
11
* @return {ListNode}
12
*/
13
const
mergeTwoLists
=
function
(
l1
,
l2
)
{
14
if
(
l1
===
null
)
{
15
return
l2
;
16
}
17
if
(
l2
===
null
)
{
18
return
l1
;
19
}
20
if
(
l1
.
val
<
l2
.
val
)
{
21
l1
.
next
=
mergeTwoLists
(
l1
.
next
,
l2
);
22
return
l1
;
23
}
else
{
24
l2
.
next
=
mergeTwoLists
(
l1
,
l2
.
next
);
25
return
l2
;
26
}
27
};
Copied!
复杂度分析
M、N 是两条链表 l1、l2 的长度
时间复杂度:$O(M+N)$
空间复杂度:$O(M+N)$
扩展
你可以使用迭代的方式求解么?
迭代的 CPP 代码如下:
1
class
Solution
{
2
public
:
3
ListNode
*
mergeTwoLists
(
ListNode
*
a
,
ListNode
*
b
)
{
4
ListNode head
,
*
tail
=
&
head
;
5
while
(
a
&&
b
)
{
6
if
(
a
->
val
<=
b
->
val
)
{
7
tail
->
next
=
a
;
8
a
=
a
->
next
;
9
}
else
{
10
tail
->
next
=
b
;
11
b
=
b
->
next
;
12
}
13
tail
=
tail
->
next
;
14
}
15
tail
->
next
=
a
?
a
:
b
;
16
return
head
.
next
;
17
}
18
};
Copied!
迭代的 JS 代码如下:
1
var
mergeTwoLists
=
function
(
l1
,
l2
)
{
2
const
prehead
=
new
ListNode
(
-
1
);
3
4
let
prev
=
prehead
;
5
while
(
l1
!=
null
&&
l2
!=
null
)
{
6
if
(
l1
.
val
<=
l2
.
val
)
{
7
prev
.
next
=
l1
;
8
l1
=
l1
.
next
;
9
}
else
{
10
prev
.
next
=
l2
;
11
l2
=
l2
.
next
;
12
}
13
prev
=
prev
.
next
;
14
}
15
prev
.
next
=
l1
===
null
?
l2
:
l1
;
16
17
return
prehead
.
next
;
18
};
Copied!
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:
https://github.com/azl397985856/leetcode
。 目前已经 40K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
以前
0020. 有效的括号
下一个
0026. 删除排序数组中的重复项
最近更新
1yr ago
复制链接
内容
题目地址(21. 合并两个有序链表)
题目描述
前置知识
公司
公司
思路
关键点
代码
扩展