力扣-21. 合并两个有序链表（Merge Two Sorted Lists）

最后编辑于2025-07-10

21. 合并两个有序链表（Merge Two Sorted Lists）

Easy

给定两个按非递减顺序排序的链表 list1 和 list2 的头结点，将它们合并为一个新的有序链表，并返回合并后的头结点。合并应通过拼接原链表节点完成（不新建节点）。

示例：

alt text

  • 输入：list1 = [1,2,4], list2 = [1,3,4] → 输出：[1,1,2,3,4,4]
  • 输入：list1 = [], list2 = [] → 输出：[]
  • 输入：list1 = [], list2 = [0] → 输出：[0]

约束：

  • 两个链表节点数之和在 [0, 100] 范围内（题目原限制为各自 [0,50]）。
  • -100 <= Node.val <= 100。
  • 两个输入链表均已按非递减顺序排序。

思路

此题与合并有序数组类似，核心思想是：在两个链表上同时遍历，每次比较当前节点的值，将较小的节点接到结果链表末尾。因为链表操作拼接成本低且不需要随机访问，用指针即可方便实现。常见实现有两种：迭代（使用虚拟头节点）与递归。

方法一：迭代（使用哑节点，推荐）

  • 创建哑节点 dummy，指针 cur 指向 dummy。
  • 当 list1 和 list2 都不为空时：比较 list1->val 与 list2->val，把较小者接到 cur->next，并将对应链表向前移动一步，同时 cur 也向前。
  • 循环结束后，将非空的剩余链表直接接到 cur->next。
  • 返回 dummy.next。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(-1);
        ListNode* cur = &dummy;
        while (list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1;
                list1 = list1->next;
            } else {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 ? list1 : list2;
        return dummy.next;
    }
};
  • 时间复杂度： O(m + n)
  • 空间复杂度： O(1)（原地操作，不计返回链表）

方法二：递归（简洁）

  • 若 list1 为空，返回 list2；若 list2 为空，返回 list1。
  • 比较 list1->val 与 list2->val：取较小者为当前头节点，然后递归合并其余部分，最后返回头节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1) return list2;
        if (!list2) return list1;
        if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};
  • 说明： 递归写法清爽，但会占用递归栈，最坏 O(m + n) 的栈深度。

作者想说的话：
合并两个有序链表的核心是同步遍历并选择较小节点拼接。迭代版本使用哑节点避免了头结点的特判，性能稳定；递归版本代码简洁，更易于理解，但需注意栈深度。两种实现都很常用，根据实际场景选用即可。