64 lines
1.2 KiB
Markdown
64 lines
1.2 KiB
Markdown
|
## 题目地址
|
|||
|
|
https://leetcode-cn.com/problems/merge-two-sorted-lists
|
|||
|
|
|
|||
|
|
## 题目描述
|
|||
|
|
```
|
|||
|
|
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
|
|||
|
|
|
|||
|
|
示例：
|
|||
|
|
|
|||
|
|
输入：1->2->4, 1->3->4
|
|||
|
|
输出：1->1->2->3->4->4
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 思路
|
|||
|
|
使用递归来解题，将两个链表头部较小的一个与剩下的元素合并，并返回排好序的链表头，当两条链表中的一条为空时终止递归。
|
|||
|
|
|
|||
|
|
|
|||
|
|
## 关键点
|
|||
|
|
|
|||
|
|
- 掌握链表数据结构
|
|||
|
|
- 考虑边界情况
|
|||
|
|
|
|||
|
|
## 代码
|
|||
|
|
* 语言支持：JS
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
/**
|
|||
|
|
* Definition for singly-linked list.
|
|||
|
|
* function ListNode(val) {
|
|||
|
|
* this.val = val;
|
|||
|
|
* this.next = null;
|
|||
|
|
* }
|
|||
|
|
*/
|
|||
|
|
/**
|
|||
|
|
* @param {ListNode} l1
|
|||
|
|
* @param {ListNode} l2
|
|||
|
|
* @return {ListNode}
|
|||
|
|
*/
|
|||
|
|
const mergeTwoLists = function (l1, l2) {
|
|||
|
|
if (l1 === null) {
|
|||
|
|
return l2;
|
|||
|
|
}
|
|||
|
|
if (l2 === null) {
|
|||
|
|
return l1;
|
|||
|
|
}
|
|||
|
|
if (l1.val < l2.val) {
|
|||
|
|
l1.next = mergeTwoLists(l1.next, l2);
|
|||
|
|
return l1;
|
|||
|
|
} else {
|
|||
|
|
l2.next = mergeTwoLists(l1, l2.next);
|
|||
|
|
return l2;
|
|||
|
|
}
|
|||
|
|
};
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
***复杂度分析***
|
|||
|
|
|
|||
|
|
M、N 是两条链表 l1、l2 的长度
|
|||
|
|
|
|||
|
|
- 时间复杂度：O(M+N)
|
|||
|
|
- 空间复杂度：O(M+N)
|
|||
|
|
|