对递归的一些理解。力扣206题：翻转链表
今天在刷力扣的时候，在写一道翻转链表的题目的过程中，在尝试使用递归解决该问题的时候，第一版代码却每次都返回的是null，这个错误让我尝试去debug了一下，最终找出了问题，并且让我对递归有了一些更深的理解，下面是我一开始写的代码。
/*** Definition for singly-linked list.* 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; }* }*/
class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; reverse(pre, cur); return pre; } public void reverse(ListNode pre, ListNode cur) { if (cur == null) { // 递归基，当cur为空时，表示已到达链表末尾，直接返回 return; } ListNode next = cur.next; // 保存当前节点的下一个节点 cur.next = pre; // 反转当前节点的指向 reverse(cur, next); // 递归地处理下一个节点 }
}我考虑的是java中的链表传递的是引用所以我在reverse递归结束后，pre应该正好是翻转链表后的第一个结点，所以我在递归后将它返回给最终答案，结果无论输入是什么，输出都是null。
在debug后，我发现，
在最后检测到cur是null之时，pre所指向的链表是我们最后要得到的答案，在这个时候执行return，但是return到的是上一个reverse函数栈，在该函数中，pre链表的结果还不是最终答案，就这样一步步回退回去之后，直到恢复成了原样，并从最后的“}}”退出，此时pre又变成了原来的空值，所以这就导致了无论我的输入是什么，输出都是空值的原因。
将代码修改如下，在最后找到目标答案值得时候，一层层返回这个答案值，而不是返回空值得回退，这样可以将最后得答案值返回给进入循环时的pre，修改后的代码如下所示。
/*** Definition for singly-linked list.* 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; }* }*/
class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; return reverse(pre, cur); } public ListNode reverse(ListNode pre, ListNode cur) { if (cur == null) { // 递归基，当cur为空时，表示已到达链表末尾，直接返回 return pre; } ListNode next = cur.next; // 保存当前节点的下一个节点 cur.next = pre; // 反转当前节点的指向 return reverse(cur, next); // 递归地处理下一个节点 }
}