LeetCode 21：合并两个有序链表（Merge Two Sorted Lists）题解

Merge Two Sorted Lists 是 LeetCode Hot 100 里一道非常经典的链表题。

这道题本身并不难，但它非常适合用来训练链表递归的思维。很多人刚开始做链表题时，往往更习惯用循环和指针一点点往后处理；而这道题除了迭代写法之外，还有一种非常优雅的解法，就是你给出的这份 递归写法。

递归版本的代码通常会显得非常短，但如果没有真正理解“每一层递归到底在做什么”，就很容易觉得它像是在“直接套公式”。实际上，这道题的递归思路非常自然： 每次只比较两个链表当前头结点中较小的那个，让它作为新链表的当前结点，然后把剩余部分交给递归继续处理。

本文就结合你这段 Java 代码，系统地讲一下这道题的思路。

题目介绍

给你两个升序链表 list1 和 list2，要求你将这两个链表合并成一个新的升序链表，并返回合并后的头结点。

注意这里有两个关键词：

1. 两个链表本身已经是 有序 的

2. 合并后得到的链表也必须保持 有序

例如：

list1 = 1 -> 2 -> 4
list2 = 1 -> 3 -> 4

合并之后应该得到：

1 -> 1 -> 2 -> 3 -> 4 -> 4

这道题的关键就在于： 我们要一边比较两个链表当前的头结点，一边把较小的结点接到答案链表后面。

示例

示例 1

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

两个链表都是升序的，所以每次比较当前头结点，把更小的那个先放进结果链表里即可。

示例 2

输入：list1 = [], list2 = []
输出：[]

两个链表都为空，合并之后自然还是空链表。

示例 3

输入：list1 = [], list2 = [0]
输出：[0]

其中一个链表为空，那么结果其实就是另一个链表本身。

最容易想到的思路

如果我们先不考虑递归，那么最直接的想法其实是：

• 创建一个新的哑结点 dummy

• 用一个指针不断比较 list1 和 list2 的当前结点

• 谁更小，就把谁接到结果链表后面

• 最后把剩下没处理完的那一段直接接上去

这是这道题非常经典的迭代解法。

不过你给出的代码走的是另一条路： 递归

而递归写法在这道题里其实特别简洁，因为它天然符合问题结构。

核心思路：递归怎么想？

我们来换一个角度思考。

假设现在有两个有序链表：

list1 = 1 -> 2 -> 4
list2 = 1 -> 3 -> 4

如果我们只看当前这两个头结点：

• list1.val = 1

• list2.val = 1

那么合并后的链表头结点，一定是这两个结点中较小的那个。 如果两者相等，选哪一个都可以，只要后续继续保持有序即可。

也就是说，这道题每一步其实只需要解决一个局部问题：

当前两个头结点谁更小？

• 如果 list1.val < list2.val，那么答案链表的头就是 list1

• 否则，答案链表的头就是 list2

而在确定了头结点之后，剩下的部分其实还是一个“合并两个有序链表”的同类问题。

这就是递归最适合出场的地方。

Java 代码

下面是你给出的代码，我这里保留原本逻辑，并加上注释：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 如果 list1 为空，直接返回 list2
        if (list1 == null) return list2;
​
        // 如果 list2 为空，直接返回 list1
        if (list2 == null) return list1;
​
        // 比较两个链表头结点的值
        if (list1.val < list2.val) {
            // list1 当前结点更小，它应该作为合并后链表的头
            // 它的 next 应该指向后续合并结果
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            // list2 当前结点更小，或者两者相等
            // 那么它作为当前头结点
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

代码拆解

这段代码非常短，但里面其实包含了递归写法最核心的思想。 下面一步一步来看。

1. 为什么先判断空链表？

if (list1 == null) return list2;
if (list2 == null) return list1;

这是递归的边界条件。

因为当某一个链表已经走完时，剩下的事情就非常简单了：

• 如果 list1 为空，那合并结果其实就是 list2

• 如果 list2 为空，那合并结果其实就是 list1

为什么可以直接返回？

因为题目已经保证两个链表本身都是升序的。 当其中一个链表空了，另一个链表剩下的部分一定也还是有序的，直接接到结果后面就可以。

所以这两句代码，实际上就是递归的终止条件。

2. 为什么只比较头结点？

if (list1.val < list2.val)

因为两个链表都是升序的。

这意味着：

• list1 当前结点后面的元素，只会大于等于 list1.val

• list2 当前结点后面的元素，只会大于等于 list2.val

所以谁的头结点更小，谁就一定应该排在当前结果链表的最前面。

这一点非常关键。 正是因为链表有序，我们才可以只通过比较当前头结点，就安全地决定当前答案的头是谁。

如果链表不是有序的，那这种做法就不成立了。

3. 为什么 list1.next = mergeTwoLists(list1.next, list2)？

list1.next = mergeTwoLists(list1.next, list2);
return list1;

假设当前情况是：

list1.val < list2.val

那么说明当前结果链表的第一个结点应该是 list1。

但是 list1 后面应该接什么呢？

答案是：

把 list1.next 和 list2 再继续合并。

因为当前 list1 已经被选为结果头结点了，它就不需要再参与后面的比较。 真正剩下还没合并的部分，是：

• list1 的后半段：list1.next

• list2 的全部

而这恰好又是一个同样的问题：

合并两个有序链表

所以直接递归调用即可。

4. 为什么另一边也是同样逻辑？

list2.next = mergeTwoLists(list1, list2.next);
return list2;

如果当前：

list1.val >= list2.val

那么当前头结点应该选 list2。

此时剩余还没处理的部分就是：

• list1

• list2.next

所以递归写成：

mergeTwoLists(list1, list2.next)

然后把返回结果接到 list2.next 上。

整个过程和前一种情况完全对称。

手动模拟一遍

我们用经典样例来走一遍：

list1 = 1 -> 2 -> 4
list2 = 1 -> 3 -> 4

第一步

比较两个头结点：

• list1.val = 1

• list2.val = 1

由于代码里写的是：

if (list1.val < list2.val)

这里只在严格小于时选择 list1，否则会走 else，所以这一轮选的是 list2。

于是当前结果头结点先确定为：

1(list2)

然后递归去处理：

mergeTwoLists(list1, list2.next)

也就是：

mergeTwoLists(1 -> 2 -> 4, 3 -> 4)

第二步

现在比较：

• list1.val = 1

• list2.val = 3

因为 1 < 3，这一轮选 list1。

当前结果继续变成：

1(list2) -> 1(list1)

然后递归处理：

mergeTwoLists(2 -> 4, 3 -> 4)

第三步

比较：

• 2

• 3

选 2，继续递归：

mergeTwoLists(4, 3 -> 4)

第四步

比较：

• 4

• 3

选 3，继续递归：

mergeTwoLists(4, 4)

第五步

比较：

• 4

• 4

由于不满足 <，所以走 else，选 list2 的 4，继续递归：

mergeTwoLists(4, null)

第六步

这时 list2 == null，直接返回 list1，也就是最后那个 4。

最终整条链表回溯拼接起来就是：

1 -> 1 -> 2 -> 3 -> 4 -> 4

为什么递归返回值就是合并后链表的头结点？

这是很多人第一次看递归链表题时最容易困惑的地方。

你可以这样理解：

mergeTwoLists(list1, list2) 这个函数的含义就是：

返回 list1 和 list2 合并之后的新链表头结点。

所以：

• 当某一层决定当前头结点是 list1 时，它就返回 list1

• 当某一层决定当前头结点是 list2 时，它就返回 list2

而这两个头结点的 next，都通过递归结果来补全。

这样一层层往下递归，再一层层返回时，整条链表就被自然串起来了。

复杂度分析

时间复杂度

每个结点都会被访问一次，因此时间复杂度是：

O(m + n)

其中：

• m 是 list1 的长度

• n 是 list2 的长度

空间复杂度

递归调用会占用函数栈空间，最坏情况下递归深度是：

m + n

所以空间复杂度是：

O(m + n)

这一点和迭代写法不同。 如果用迭代法，额外空间可以做到 O(1)；而递归法会额外消耗栈空间。

这道题真正想考什么？

这道题表面上是在考链表合并，但本质上它非常适合训练两个能力：

第一，是否能利用“有序”这个条件

因为两个链表本身已经有序，所以每次只比较当前头结点，就可以确定当前谁应该排在前面。

这说明：

有序性往往意味着可以做局部决策。

第二，是否能理解链表递归

很多树和链表题，其实都很适合用递归来写。 难点不在于代码多复杂，而在于你能不能把问题拆成：

• 当前这一层做什么

• 剩下的问题交给谁处理

这道题几乎是链表递归里最经典的入门题之一。

递归写法和迭代写法怎么选？

这道题常见有两种写法：

递归写法

优点：

• 代码短

• 逻辑清晰

• 很适合帮助理解问题结构

缺点：

• 额外消耗递归栈空间

迭代写法

优点：

• 空间复杂度更低

• 更适合处理很长的链表

缺点：

• 代码会稍微长一些

• 指针操作更繁琐一点

如果是刷题和理解思路，我个人觉得递归版本特别值得掌握。 因为它能帮助你建立“链表问题也可以递归地思考”这种意识。

总结

这道题的核心思路其实非常简单：

1. 如果某个链表为空，直接返回另一个链表

2. 否则比较两个链表当前头结点

3. 较小的那个结点作为当前结果链表的头

4. 它的 next 指向剩余部分的合并结果

5. 递归继续处理，直到某一边为空

所以这道题的本质就是：

每次只解决当前头结点该选谁，剩下的问题继续递归。

它是一道非常标准、也非常漂亮的链表递归题。 如果你刚开始学链表递归，建议一定要把这道题真正理解透，尤其要想清楚：

• 每一层递归返回的到底是什么

• 为什么只比较当前头结点就够了

• 为什么递归结果能自然拼成完整链表

把这道题吃透之后，你再去看：

• 反转链表

• 两两交换链表中的节点

• 合并 K 个升序链表

这些题时，理解会顺很多。

因为“合并两个有序链表”，本身就是链表递归里非常重要的一块基础模板。