对递归的一些理解。力扣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); // 递归地处理下一个节点  }  
}