206. 反转链表
206. 反转链表
分析
所谓反转，其实就是反转指针，将 A->B 变成 A<-B。做法也很简单：
一开始的时候是 A 节点的 next 指针指向 B，B 节点的 next 指针指向 null 。反转就是让 B 节点的 next 指针指向 A，同时 A 节点的 next 指针指向 null，注意更新 A 的 next 指针很有必要，不然就会变成 A<->B。比如，链表的最后一个节点（原链表的 head）的 next 指针会指向倒数第二个节点，而倒数第二个节点已经指向了最后一个节点，于是形成了回环。
如果 B 还指向了别的节点，比如 A->B->C ，那么就先反转 B 跟 C 的指针关系，再反转 A 跟 B 的指针，也就是先反转链表末尾的相邻元素，再反转链表前端的相邻元素。
很有意思的一点是，我们需要返回新的链表的头节点，即原链表的最后一个节点（这也是递归的终止条件），我们需要将这个节点传递到最上层的递归调用，这就出现了一个很有意思的事情，就是，每一递归都是将其递归调用子节点的结果返回，这个结果跟本轮递归的反转指针的操作是不相干的。而一般情况下，递归返回的结果跟递归内做的操作都是有关系的。
递归三步分析法
其实递归没有那么复杂，但是总写不好，三道题套路解决递归问题 这篇博客就写的很好，
递归的过程如下：
递归是一个反复调用自身的过程，这就说明它每一级的功能都是一样的，因此我们只需要关注一级递归的解决过程即可。
如上图所示，我们需要关心的主要是以下三点：这也是我们写递归的编码顺序。
- 整个递归的终止条件，递归应该在什么时候结束？
- 本级递归应该做什么，在这一级递归中，应该完成什么任务？
- 找返回值，应该返回给上一级的返回值是什么？
一定要理解这 3 步，这就是以后递归秒杀算法题的依据和思路。
我们写这一题，对号入座。
- 终止条件，找到最后一个节点
- 本机递归应该做什么：反转两个节点（设置 next 指针）
- 返回值：反转之后的头节点
解题
public ListNode reverseList(ListNode head) {
// 如果输入为 null，那么也返回 null
// next指针为空，说明是最后一个节点，也就是反转之后的新的head
if(head==null || head.next==null){
return head;
}
// 得先反转下一个节点的，然后再反转自己这个节点的，不然先反转自己这个节点，下一个节点就不对了
ListNode newHead = reverseList(head.next);
// 反转分两步
// 第一步把下一个节点的next指针指向当前节点
head.next.next=head;
//第二步把当前节点的next设置为 null
// 如果不设置为null，head 和 head.next 的 next指针就会指向对方，变成回环
// 因为之前已经获取了 head.next，所以这里设置为null不影响
// 而且 head.next会 当前节点的前一个节点的reverseList方法中再次被赋值
head.next=null;
return newHead;
}
其实我自己的一个重要经验就是，只要你==梳理清楚最后一次递归（整个递归终止）和倒数第二次递归的衔接==，整个递归你就清楚了。