> For the complete documentation index, see [llms.txt](https://suki.gitbook.io/91-days-algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://suki.gitbook.io/91-days-algorithm/problems/0021.merge-two-sorted-lists.md).

# 21. 合并两个有序链表

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

* [21. 合并两个有序链表](https://suki.gitbook.io/91-days-algorithm/problems/pages/-MfogIylBgE9XIrthi0I#21-合并两个有序链表)
  * [题目描述](https://suki.gitbook.io/91-days-algorithm/problems/pages/-MfogIylBgE9XIrthi0I#题目描述)
  * [方法 1: 迭代](https://suki.gitbook.io/91-days-algorithm/problems/pages/-MfogIylBgE9XIrthi0I#方法-1-迭代)
    * [思路](https://suki.gitbook.io/91-days-algorithm/problems/pages/-MfogIylBgE9XIrthi0I#思路)
    * [复杂度分析](https://suki.gitbook.io/91-days-algorithm/problems/pages/-MfogIylBgE9XIrthi0I#复杂度分析)
    * [代码(JavaScript/C++)](https://suki.gitbook.io/91-days-algorithm/problems/pages/-MfogIylBgE9XIrthi0I#代码javascriptc)
  * [方法 2: 递归](https://suki.gitbook.io/91-days-algorithm/problems/pages/-MfogIylBgE9XIrthi0I#方法-2-递归)
    * [思路](https://suki.gitbook.io/91-days-algorithm/problems/pages/-MfogIylBgE9XIrthi0I#思路-1)
    * [复杂度分析](https://suki.gitbook.io/91-days-algorithm/problems/pages/-MfogIylBgE9XIrthi0I#复杂度分析-1)
    * [代码(JavaScript/C++)](https://suki.gitbook.io/91-days-algorithm/problems/pages/-MfogIylBgE9XIrthi0I#代码javascriptc-1)

## 题目描述

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

示例：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```

## 方法 1: 迭代

### 思路

* 用两个指针分别遍历两个链表，比较两个指针节点的大小。
  * 将较小的那个节点加到新链表中，然后指针后移。
  * 较大的那个节点指针不动，下一轮继续比较。
* 如果两个链表长度不一样，继续遍历将多出来的节点加到新链表中就好了。

### 复杂度分析

* 时间复杂度：$O(N)$, N 为新链表长度。
* 空间复杂度：$O(1)$。

### 代码(JavaScript/C++)

JavaScript Code

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
    const dummy = new ListNode();
    let p1 = l1,
        p2 = l2,
        cur = dummy;

    while (p1 || p2) {
        if (!p2 || (p1 && p1.val <= p2.val)) {
            cur.next = new ListNode(p1.val);
            p1 = p1.next;
        } else {
            cur.next = new ListNode(p2.val);
            p2 = p2.next;
        }
        cur = cur.next;
    }

    return dummy.next;
};
```

C++ Code

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(0);
        ListNode *tail = dummy;

        while (l1 && l2) {
            if (l1->val <= l2->val) {
                tail->next = new ListNode(l1->val);
                l1 = l1->next;
            } else {
                tail->next = new ListNode(l2->val);
                l2 = l2->next;
            }
            tail = tail->next;
        }
        while (l1) {
            tail->next = new ListNode(l1->val);
            l1 = l1->next;
            tail = tail->next;
        }
        while (l2) {
            tail->next = new ListNode(l2->val);
            l2 = l2->next;
            tail = tail->next;
        }
        return dummy->next;
    }
};
```

## 方法 2: 递归

### 思路

* 如果 `l1.val < l2.val`，那就把 l1 作为合并链表的头部返回，然后继续合并 `l1.next` 和 `l2` 之后的节点。
* 如果 `l1.val > l2.val`，那就把 l2 作为合并链表的头部返回，然后继续合并 `l2.next` 和 `l1` 之后的节点。
* 递归出口：
  * 没有节点了。
  * 只剩一个节点，直接返回。

### 复杂度分析

* 时间复杂度：$O(N)$, N 为新链表长度。
* 空间复杂度：$O(N)$, N 为新链表长度，递归栈的空间。

### 代码(JavaScript/C++)

JavaScript Code

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};
```

C++ Code

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;

        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};
```

更多题解可以访问：<https://github.com/suukii/91-days-algorithm>