0021. 合并两个有序链表
题目地址(21. 合并两个有序链表)
题目描述
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 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
最近更新 1yr ago