算法

合并两个有序链表

loser

22 Aug 2026 • 7 min read

将两个升序链表 l1 和 l2 合并为一个新的升序链表并返回。

新链表是通过拼接给定的两个链表的所有节点组成的，不需要创建新的数据节点。

两个链表都按照非递减顺序排列，也就是允许存在相等的节点值。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列

解法一（迭代）：

/**
 * 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* list1, ListNode* list2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;

        while (list1 != nullptr && list2 != nullptr)
        {
            if (list1->val <= list2->val)
            {
                tail->next = list1;
                list1 = list1->next;
            }
            else
            {
                tail->next = list2;
                list2 = list2->next;
            }

            tail = tail->next;
        }

        if (list1 != nullptr)
        {
            tail->next = list1;
        }
        else
        {
            tail->next = list2;
        }

        return dummy.next;
    }
};

解法二（递归）：

/**
 * 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* list1, ListNode* list2) {
        if (list1 == nullptr)
        {
            return list2;
        }

        if (list2 == nullptr)
        {
            return list1;
        }

        if (list1->val <= list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }

        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
};

核心思想

两个链表本身已经有序，所以不需要把所有节点放入数组后再排序。

只需要比较两个链表当前头节点的值，把较小的节点接到合并链表的末尾，然后让对应链表向后移动。

这题最关键的观察是：

两个有序链表的当前头节点中，较小的那个一定是合并后链表当前应该选择的节点。

因为两个链表后面的节点都不小于各自当前节点，所以较大的当前节点不可能排在较小当前节点之前。

重复这个过程，直到其中一个链表为空。

此时另一个链表剩下的部分本身已经有序，可以直接接到合并链表末尾。

解法一：迭代合并

使用一个虚拟头节点 dummy，它不属于最终结果，只是为了方便处理合并链表的第一个节点。

ListNode dummy(0);
ListNode* tail = &dummy;

其中：

dummy.next 是最终合并链表的头节点
tail 指向当前合并链表的最后一个节点

每次比较：

list1->val <= list2->val

如果 list1 的值更小或相等，就把 list1 接到 tail 后面。

否则就把 list2 接到 tail 后面。

接入节点后，两个指针分别向后移动：

list1 = list1->next;

或者：

list2 = list2->next;

最后让 tail 移动到新接入的节点：

tail = tail->next;

为什么可以直接接上剩余链表

当循环结束时，至少有一个链表为空。

假设 list1 == nullptr，说明 list1 中所有节点都已经被合并。

list2 剩余的节点仍然按照非递减顺序排列。

并且，合并链表最后一个已经选择的节点不大于 list2 当前头节点。

所以可以直接执行：

tail->next = list2;

不需要继续逐个处理剩余节点。

list2 剩余部分本身就是有序的，直接拼接不会破坏整体有序性。

解法二：递归合并

递归方法仍然比较两个链表的头节点。

如果：

list1->val <= list2->val

那么 list1 一定是合并后链表的第一个节点。

接下来只需要递归合并：

list1->next 和 list2

也就是：

list1->next = mergeTwoLists(list1->next, list2);

如果 list2 的头节点更小，则同理：

list2->next = mergeTwoLists(list1, list2->next);

递归终止条件是某个链表为空。

此时直接返回另一个链表，因为另一个链表剩余部分已经有序。

相等元素如何处理

代码中使用：

list1->val <= list2->val

当两个节点值相等时，优先选择 list1。

选择哪一个都不会影响最终的值序列，因为它们的值相同。

使用 <= 还可以保证相等节点能够被正常接入，不会漏掉任何节点。

边界情况

如果两个链表都为空：

l1 = []
l2 = []

迭代解法中，循环不会执行，dummy.next 是 nullptr。

递归解法中，直接返回 list2，也就是 nullptr。

如果只有 list1 为空，直接返回 list2。

如果只有 list2 为空，直接返回 list1。

如果链表只有一个节点，也可以按照相同逻辑处理，不需要单独编写特殊代码。

正确性证明

我们证明：算法返回的链表包含两个输入链表的全部节点，并且按照非递减顺序排列。

结论 1：每次选择的节点都是当前所有未处理节点中的最小值

设当前两个链表头节点分别为 list1 和 list2。

因为两个链表都是非递减排列，所以：

list1 后面的节点都不小于 list1->val
list2 后面的节点都不小于 list2->val

如果 list1->val <= list2->val，那么 list1->val 不大于两个链表中任何未处理节点的值。

所以选择 list1 是安全的。

如果 list2->val < list1->val，同理，选择 list2 是安全的。

因此每次选择的节点都是当前未处理节点中的最小值。

结论 2：合并过程中，已经形成的链表始终保持非递减顺序

第一次接入的节点是当前两个链表头节点中的较小者。

之后每次接入的节点都不小于当前未处理节点中的最小值，而当前未处理节点中的最小值不小于已经接入链表的最后一个节点。

所以每次新接入的节点都不小于 tail，合并链表始终保持非递减顺序。

结论 3：算法不会遗漏或重复节点

每次选择一个节点后，只移动被选择节点所在链表的指针。

因此被选择的节点会被接入一次，并且不会再次参与比较。

当一个链表为空时，另一个链表中剩余的所有节点会被整体接到结果末尾。

所以两个输入链表中的每个节点都恰好出现在合并结果中一次。

结论 4：递归方法与迭代方法具有相同的选择逻辑

递归方法同样比较两个当前头节点，并把较小的节点作为当前结果头节点。

然后递归处理剩余节点。

因此每一层递归都满足结论 1、结论 2 和结论 3。

递归结束时，剩余链表直接返回，也符合合并逻辑。

得出结论

由结论 1 可知，每次选择的节点都不会破坏最终的升序排列。

由结论 2 可知，合并过程始终保持非递减顺序。

由结论 3 可知，两个链表的所有节点都被完整且不重复地加入结果。

由结论 4 可知，递归方法同样正确。

因此两个解法都能正确合并两个有序链表。

举例理解

以：

l1 = [1,2,4]
l2 = [1,3,4]

为例。

迭代合并过程如下：

`l1` 当前值	`l2` 当前值	选择节点	合并结果
`1`	`1`	`l1` 的 `1`	`[1]`
`2`	`1`	`l2` 的 `1`	`[1,1]`
`2`	`3`	`l1` 的 `2`	`[1,1,2]`
`4`	`3`	`l2` 的 `3`	`[1,1,2,3]`
`4`	`4`	`l1` 的 `4`	`[1,1,2,3,4]`

此时 l1 为空，直接接上 l2 剩余的 4。

最终结果是：

[1,1,2,3,4,4]

复杂度分析

设两个链表的节点数分别为 m 和 n。

每个节点最多被访问和接入一次。

解法一

时间复杂度：O(m + n)
空间复杂度：O(1)

解法二

递归调用次数最多为 m + n，递归栈深度也是 O(m + n)。

时间复杂度：O(m + n)
空间复杂度：O(m + n)

迭代解法不需要递归栈，空间复杂度更优，是更推荐的做法。