Java递归反转链表时newHead参数未跨栈同步问题求解

基于递归实现的链表反转代码运行未达预期，调试发现各层递归调用内的修改无法传递到其他栈帧：

• 测试链表结构为1->2->null，递归调用顺序依次为reverse(null,1,null)、reverse(1,2,null)、reverse(2,null,null)
• 预期递归边界触发时newHead会被赋值为节点2，且因为传入的是引用，该赋值应该在所有栈层生效；实际退出边界层后，上层栈内的newHead仍然为null，修改没有同步。

原始代码如下：

public class ListNode {
 int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 
 public static ListNode reverseList(ListNode head) {
    if(head==null){
        return null;
    }
        ListNode newHead = head;
        reverse(null,head,newHead);
        return newHead;
        
    }
    
    private static void reverse(ListNode prev, ListNode curr, ListNode newHead){
        if(curr==null){
            newHead = prev;
            return;
        }
        reverse(curr,curr.next,newHead);
        curr.next = prev;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1,new ListNode(2));
        reverseList(head);
        System.out.print(head.val);
    }
}

Java所有参数传递都是值传递，引用类型参数传递的是对象内存地址的副本，不是引用本身：

• 每个递归栈帧内的newHead都是当前方法的独立局部变量，仅存了一份地址拷贝
• 递归边界处执行newHead = prev时，只是修改了当前最底层栈帧内局部变量的指向，既没有修改上层栈帧的同名局部变量，也没有修改任何对象的成员属性
• 最底层方法出栈后，该局部变量直接销毁，上层栈帧内的newHead仍然保留旧值，自然感知不到这次赋值。

另外main方法的打印逻辑也有问题：链表反转完成后原head节点会变成尾节点，直接打印原head的val永远拿不到新的头节点值。

最规范的实现是让递归方法携带返回值，把递归边界拿到的新头节点逐层向上返回，不需要靠参数透传。修正后代码如下：

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 
    public static ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        return reverse(null, head);
    }
    
    private static ListNode reverse(ListNode prev, ListNode curr){
        // 递归边界：curr为null时prev就是反转后的新头
        if(curr == null){
            return prev;
        }
        // 先递归处理后续节点，拿到新头
        ListNode newHead = reverse(curr, curr.next);
        // 反转当前节点的指针
        curr.next = prev;
        // 新头原封不动向上返回
        return newHead;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1,new ListNode(2));
        ListNode newHead = reverseList(head);
        // 打印新头节点的值，输出结果为2
        System.out.print(newHead.val);
    }
}

• 指针反转的核心逻辑curr.next = prev和原有实现完全一致，不需要改动
• 新头节点只在递归边界处产生一次，后续所有递归层只需要把这个值原封不动返回给上层即可，不需要额外存储
• 这种实现没有额外的全局变量，方法封装性更好，也是递归反转链表的标准写法。

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