【递归】反转链表，你掌握了吗？

206. 反转链表

206. 反转链表

​ 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

img

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

img

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

进阶： 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解题思路：递归

​ 对于链表，其实用迭代的方式是比较好理解的，因为把它抽象成一棵二叉树，其实就是一个单分支的二叉树，所以用迭代反而会更好理解，但是为了学习递归，我们要使用递归的思想来解决这道题，其实也不是很难，就是一个逆序的时机问题！

​

​ 递归问题，我们要用宏观的角度去看待，只要发现了重复的子问题，我们就把其中的一个子问题拎出来处理，然后交给其它子问题去解决即可，就像这道题的例一，我们要对整个链表进行逆序，如果我们针对前两个节点单独来说的话，将节点二直接指向节点一的话，那么节点三就丢失了，所以我们要换个思路，就是递归的思路，在处理前两个节点之前，应该先保证后面的节点已经处理完逆序了，此时就只需要关心当前的两个节点即可，如下图所示：

​ 可以看到，按照上面的操作次序来看，这就是一个 后序遍历，先递归处理后面的节点，再返回来完成当前节点的操作！

​ 只不过要注意一个细节，就是题目要返回的是逆序后新的头节点也就是节点五，如果我们在递归函数中返回当前节点，那最后得到的还是上图中的节点一，所以我们需要 在后序遍历到空节点的时候，也就是在递归函数的出口记录下节点五，然后进行返回，经过一层一层的返回之后，最后在原先调用递归函数的入口处就拿到了新节点，进行返回即可！

​ 此外，因为最后我们要让原来的头节点指向空，那么递归函数中就需要有一个操作是把 cur->next 指向空的，这对深层的其它节点其实是没有影响的，因为中间的某些节点在操作的时候虽然也是直接 cur->next = nullptr，但是操作完之后返回到上一层之后，进行操作是 cur->next->next 指向 cur，此时 cur->next->next 为空的话是没问题的！

​ 所以可以统一第三步操作为 cur->next = nullptr。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 递归函数出口
        if(head == nullptr || head->next == nullptr)
            return head;
        
        // 进行后序遍历，因为操作当前节点前要保证后面已经处理完毕。
        // 还要将返回的节点记录下来，这个节点是新的头节点
        ListNode* newhead = reverseList(head->next);

        // 操作当前节点
        head->next->next = head;
        head->next = nullptr;

        // 最后返回记录的新头节点
        return newhead;
    }
};