宏观角度认识递归之反转链表

递归之反转链表"/>

宏观角度认识递归之反转链表

206. 反转链表 - 力扣（LeetCode）

对于反转链表，如果是考虑从头到尾开始的话，就会出现：从第二个节点开始，它的next指向第一个节点，导致第三个节点失去方向，这样无法解决问题。因此考虑从尾到头开始，从宏观的角度看问题，并找到子问题；

要反转整个链表，可以让当前节点后面的链表先完成反转，然后把头结点返回，再让当前节点连接到反转后的链表后面就可以了；

1. 重复子问题 -> 函数头：当前节点后面的链表先完成反转，再连接；

2. 解析子问题 -> 函数体：当前节点后面的链表先完成反转，把当前节点连接上，并让当前节点的 next 指向 null，因为反转到第一个节点的时候，第一个节点是要指向 null 的；

3. 递归出口：当当前节点为空，或者当前节点.next 为空，就直接返回当前节点；

代码实现 

class Solution {public ListNode reverseList(ListNode head) {// 递归出口if(head == null || head.next == null){  // 此处加上head==null判断，防止空指针异常return head;                        }ListNode newHead =  reverseList(head.next);head.next.next = head;head.next = null;return newHead;}
}