## 题目地址(21. 合并两个有序链表)

https://leetcode-cn.com/problems/merge-two-sorted-lists

## 题目描述

```
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

```

## 前置知识

- [递归](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md)
- [链表](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md)

## 公司

- 阿里
- 字节
- 腾讯
- amazon
- apple
- linkedin
- microsoft

## 公司

- 阿里、字节、腾讯

## 思路

本题可以使用递归来解，将两个链表头部较小的一个与剩下的元素合并，并返回排好序的链表头，当两条链表中的一条为空时终止递归。

## 关键点

- 掌握链表数据结构
- 考虑边界情况

## 代码

- 语言支持：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)$

## 扩展

- 你可是使用迭代的方式求解么？

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
