递归反转链表执行顺序与新头节点返回机制问询

以下解析基于Java实现的最常用递归反转链表代码，所有流程对应实际代码执行顺序：

// 单链表节点定义
public class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public ListNode reverseList(ListNode head) {
    // 递归终止边界：空链表/已经走到原链表尾节点
    if (head == null || head.next == null) {
        return head;
    }
    // 递归处理当前节点之后的子链表
    ListNode newHead = reverseList(head.next);
    // 反转当前节点和后继节点的指针
    head.next.next = head;
    head.next = null;
    // 向上返回结果
    return newHead;
}

Q1：遍历找新头、反转指针两类操作的执行顺序 #

结论非常明确：递归会先沿着next指针一路向下走到链表最尾部，整个向下遍历的过程完全不做任何指针修改；等走到尾节点触发递归终止条件后，才会在回溯向上的过程中逐层完成指针反转，同时把新头节点往上层传递。

以测试链表1 -> 2 -> 3 -> 4 -> 5 -> null为例，完整执行流程分两个阶段：

向下递归阶段（仅遍历，不做反转） #

• 初始调用传入头节点1，判断1的next是2、不是尾节点，执行reverseList(2)，当前节点1对应的函数栈帧暂停，等待下层返回结果
• 进入节点2的栈帧，判断2的next是3、不是尾节点，执行reverseList(3)，节点2的栈帧暂停
• 进入节点3的栈帧，判断3的next是4、不是尾节点，执行reverseList(4)，节点3的栈帧暂停
• 进入节点4的栈帧，判断4的next是5、不是尾节点，执行reverseList(5)，节点4的栈帧暂停
• 进入节点5的栈帧，判断5的next是null，满足终止条件，直接将节点5作为返回值回传给节点4的栈帧。到这里向下遍历完全结束，全程没有修改过任何节点的next指向。

回溯阶段（逐对反转指针） #

• 回到节点4的栈帧，拿到下层返回的节点5，开始执行反转逻辑：将4的后继节点（也就是5）的next指向4，再把4的next设为null避免成环，此时局部链表关系为5 -> 4 -> null，节点1、2、3的指向还保持原样，之后把节点5作为返回值回传给节点3的栈帧
• 回到节点3的栈帧，拿到下层返回的节点5，执行反转：将3的后继节点（原来的4）的next指向3，3.next设为null，局部链表变为5 -> 4 -> 3 -> null，再把节点5回传给节点2的栈帧
• 回到节点2的栈帧，拿到下层返回的节点5，执行反转：将2的后继节点（原来的3）的next指向2，2.next设为null，局部链表变为5 -> 4 -> 3 -> 2 -> null，再把节点5回传给节点1的栈帧
• 回到节点1的栈帧，拿到下层返回的节点5，执行反转：将1的后继节点（原来的2）的next指向1，1.next设为null，此时完整链表变为5 -> 4 -> 3 -> 2 -> 1 -> null，再把节点5返回给最外层的初始调用，整个反转流程结束。

Q2：新头节点的逐层传递逻辑 #

新头节点本质就是原链表的尾节点，整个传递过程没有特殊逻辑，就是普通的函数返回值透传：

1. 触底生成新头：递归走到原链表尾节点时触发终止条件，此时直接把当前尾节点作为返回值，返回给调用它的上一层栈帧（也就是尾节点的直接前驱）。这是整个流程里新头节点唯一一次被“生成”的位置，后续所有层都不会修改这个值。
2. 逐层原样透传：每一层栈帧完成自己负责的两个相邻节点的指针反转后，不会对下层传上来的新头节点做任何修改，直接把它作为自己的返回值传给更上一层。比如节点4层拿到5，反转完就把5往上抛；节点3层拿到5，反转完也把5往上抛，以此类推。
3. 最终返回结果：当回溯到最顶层的初始调用栈帧时，拿到的返回值就是从最底层一路透传上来的原尾节点，也就是反转后链表的新头节点。

常见理解误区：反转逻辑的代码写在递归调用语句的后面，属于函数的后序执行位置，这部分代码必须等下层递归全部执行完、返回结果之后才会运行，所以不可能在向下遍历的阶段完成指针反转。

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