Merge Two Sorted Lists 是 LeetCode Hot 100 里一道非常经典的链表题。
这道题本身并不难，但它非常适合用来训练链表递归的思维。很多人刚开始做链表题时，往往更习惯用循环和指针一点点往后处理；而这道题除了迭代写法之外，还有一种非常优雅的解法，就是你给出的这份 递归写法
递归版本的代码通常会显得非常短，但如果没有真正理解“每一层递归到底在做什么”，就很容易觉得它像是在“直接套公式”。实际上，这道题的递归思路非常自然： 每次只比较两个链表当前头结点中较小的那个，让它作为新链表的当前结点，然后把剩余部分交给递归继续处理。
本文就结合你这段 Java 代码，系统地讲一下这道题的思路。
题目介绍
给你两个升序链表 list1 和 list2，要求你将这两个链表合并成一个新的升序链表，并返回合并后的头结点。
注意这里有两个关键词：
-
两个链表本身已经是 有序 的
-
合并后得到的链表也必须保持 有序
例如：
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)；而递归法会额外消耗栈空间。
这道题真正想考什么？
这道题表面上是在考链表合并，但本质上它非常适合训练两个能力：
第一，是否能利用“有序”这个条件
因为两个链表本身已经有序，所以每次只比较当前头结点，就可以确定当前谁应该排在前面。
这说明：
有序性往往意味着可以做局部决策。
第二，是否能理解链表递归
很多树和链表题，其实都很适合用递归来写。 难点不在于代码多复杂，而在于你能不能把问题拆成：
-
当前这一层做什么
-
剩下的问题交给谁处理
这道题几乎是链表递归里最经典的入门题之一。
递归写法和迭代写法怎么选？
这道题常见有两种写法：
递归写法
优点：
-
代码短
-
逻辑清晰
-
很适合帮助理解问题结构
缺点：
-
额外消耗递归栈空间
迭代写法
优点：
-
空间复杂度更低
-
更适合处理很长的链表
缺点：
-
代码会稍微长一些
-
指针操作更繁琐一点
如果是刷题和理解思路，我个人觉得递归版本特别值得掌握。 因为它能帮助你建立“链表问题也可以递归地思考”这种意识。
总结
这道题的核心思路其实非常简单：
-
如果某个链表为空，直接返回另一个链表
-
否则比较两个链表当前头结点
-
较小的那个结点作为当前结果链表的头
-
它的
next指向剩余部分的合并结果 -
递归继续处理，直到某一边为空
所以这道题的本质就是：
每次只解决当前头结点该选谁，剩下的问题继续递归。
它是一道非常标准、也非常漂亮的链表递归题。 如果你刚开始学链表递归，建议一定要把这道题真正理解透，尤其要想清楚：
-
每一层递归返回的到底是什么
-
为什么只比较当前头结点就够了
-
为什么递归结果能自然拼成完整链表
把这道题吃透之后，你再去看：
-
反转链表
-
两两交换链表中的节点
-
合并 K 个升序链表
这些题时，理解会顺很多。
