算法学习：递归

206. 反转链表

背景：链表

目的：反转链表

方法：递归

如果使得任意两个结点反向连接，假设这两个节点为 first 和 next ，应该有 next -> next = first ，但在这之前应该将 next 节点的下一个节点保存下来，否则将访问不到下一个节点。

处理完 first 和 next 节点之后，就应该处理 next 和已经保存的下一个节点，处理的过程和上面一样，这就形成了一个递归的过程。

递归的又一个重点是出口条件，按上文所说的递归方法，递归应该在链表末尾结束。4 和 5 两个节点反转结束后，first 节点将指向节点 5，而 next 节点会指向 nullptr，所以当 next == nullptr 时，退出递归。

最终要返回的是反转链表后的头节点，在退出递归时 first 正好指向反转前最后一个节点，返回该节点即可。

额外需要注意的是反转前的头节点，它的 next 需要指向 nullptr，不然链表会有环。

最终实现的函数如下：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr)
        {
            return head;
        }
        return reverseList(head,head->next);
    }
    ListNode* reverseList(ListNode* first,ListNode* next) {
        if(next == nullptr)
        {
            return first;
        }
        if(first->next == next)
        {
            first->next = nullptr; 
        }
        ListNode* save = next->next;
        next->next = first;
        return reverseList(next, save);
    }
};

可以更换一种递归方式。

上文当中的递归采用自底向上的思想，是从链表的首部开始遍历的，反转操作会使得某一时刻链表是中断的，无法通过 next 直接访问到未来的节点，于是需要在反转之前保存下一节点，那有没有办法让链表无法中断呢？

试想一下递归从尾部开始遍历，比如先反转 4 和 5 两个节点，再反转 3 和 4 两个节点，向下一个目的节点移动的过程可以交给递归自身来实现，并不需要我们主动去寻找下一个目的节点。

所以这个递归调用需要在反转之前完成，这是自顶向下的思想，也可以理解成深度优先的思想。

利用函数参数的性质使用递归，可以想象成在每一次递归调用时将我们要使用的量和要处理的过程 保存 下来，在栈中作为函数栈帧来展开，等到全部保存完毕（全部展开）之后再开始我们的处理，最顶部的栈帧先进行处理，处理结束之后弹出这块栈帧，栈顶永远是我们要处理的部分，直到栈空，即弹出所有栈帧，自顶向下的递归结束。

那么递归的出口如何确定，何时结束我们的递归？上文中说“全部展开”，当展开到最后一个节点时可以说明已经“全部展开”，对于最后一个节点有 next == nullptr 的特征，当然也需要考虑传入的节点为 nullptr 的情况，所以当位于以上情况时结束递归的调用，对于末尾的元素我们应该只返回它的地址，以符合题意中“返回反转之后的头部指针”。

if(!head || !head->next)
{
    return head;
}

反转的步骤，在“自底向上”的递归分析中我们可以发现 next->next = first 这里可以改变为 first->next->next = first ，于是我们的反转步骤如下

head->next->next = head;
head->next = nullptr; // 避免生成环

最终，最顶层的返回值要一直传递到最底层的调用，所以我们要把每次递归调用的结果返回，完整的代码如下：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next)
        {
            return head;
        }
        ListNode* newNode = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newNode;
    }
};

总结

这道题算是递归的入门题目，使用“自底向上”和“自顶向下”两种思想求解，解释的过程有些乱，在我熟练使用递归的思想后再来详细解释。