关于链表mergeTwoLists方法中递归逻辑的疑问与解析请求

首先看原代码：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // Base cases
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        
        // Recursive case
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

疑问解答 #

1. 该合并函数如何确保生成的链表连接正确？ #

递归的核心是拆解问题+处理当前节点+拼接子问题结果：

• 每次递归只聚焦一件事：从两个链表的当前头节点里选出值更小的那个，作为合并链的当前节点。
• 随后把这个节点的next指向剩余节点合并后的有序链表——剩余节点的合并是规模更小的子问题，递归函数会自动完成有序拼接。
• 因为原链表本身是有序的，每一步都选当前最小的节点，再衔接后续的有序子链，自然能保证整个链表的连接顺序正确且无断链。

举个简单实例：
list1: 1 -> 3 -> 5
list2: 2 -> 4 -> 6
第一次递归选1，把1.next指向merge(3->5, 2->6)的结果；
在merge(3->5,2->6)里选2，把2.next指向merge(3->5,4->6)的结果；
以此类推，每一步只负责当前节点的连接，子问题会处理后续所有节点的有序拼接，不会出现顺序混乱或连接错误。

2. 深层递归调用的返回值如何用于构建最终的合并链表？ #

递归是从底层往上层反向拼接的过程：

• 当递归到最深处时，必然触发base case：比如其中一个链表已空，直接返回另一个链表的剩余节点（本身就是有序链）。
• 上层递归拿到这个返回值后，将当前选中节点的next指向它，再把当前节点作为新的有序链表头，返回给更上层。
• 每一层的返回值都是当前子问题合并后的有序链表头，上层用这个头衔接自己选中的节点，逐步向上构建出完整的合并链表。

还是用上面的实例：
当递归到merge(null,6)时，返回6；
上层merge(5,6)选5，把5.next=6，返回5->6；
再上层merge(3->5,4->6)选3，把3.next=4->5->6（merge(5,4->6)的结果），返回3->4->5->6；
最终回到最上层，1.next=2->3->4->5->6（merge(3->5,2->6)的结果），返回1->2->3->4->5->6，就是最终的合并链表。

理解递归过程的技巧 #

• 先抓终止条件：明确base case的行为，这是整个递归的基础，也是最容易理解的部分。
• 只看当前层逻辑：不要试图一次性跟踪所有递归调用，只关注当前层要做什么：选哪个节点，把它的next指向子问题结果，返回当前节点。
• 手动走小例子：拿长度2-3的短链表，把每一步的输入、选中节点、返回值写下来，就能直观看到链表是怎么一步步拼接起来的。

内容的提问来源于stack exchange，提问作者itzTiru