labuladong刷题——第一章（2） 反转单链表 （递归）

一、递归反转整个链表

直接从代码实现看起来：

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

对于递归算法，最重要的就是明确递归函数的定义。具体来说，我们的 reverse 函数定义是这样的：输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。

 输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。也就是说会变成上述这个图的样子。

首先根据代码，从1开始确认不是null、2也不是null，所以继续向后。

该行代码会一直持续到6，因为6的next是null，所以返回的是null。

注意这里已经返回了！

所以接下来进入下一行，这里的head是5，return的仍然是6。

head指向的是6，所以我们要让6指向5，return。

进入下一行，这里head指向的是4，所以我们让5指向4，继续return。

这就是整个递归的过程。

注意搞明白return的是last，只要搞明白这一点就可以了，其实可以再思考的过程中不需要考虑递归的过程，只需要考虑中间状态。

 如图所示，reverse中间这一部分之后，就会变成下图这种情况。

 所以一定要注意，这个思考的过程是不需要考虑后面的部分是怎么来的！他只要考虑后面的过程完成就行了！这时候last是最后一位，因为一开始第一行就说明了当head==null的时候就会return成last，而last是不会变得！