反转链表（递归法）图文详解
反转链表（递归法）图文详解
链表反转是数据结构中一个经典的问题，其中递归法因其简洁优雅的特性而备受青睐。本文将通过图文结合的方式，详细讲解如何使用递归方法实现链表反转，帮助读者深入理解这一算法的核心思想。
在学习代码随想录双向指针算法时，发现卡尔的从后向前递归法反转链表，在视频和文章中都没有详细讲解。随后在网上搜索相关文章，发现大多都是文字讲解，而且一些细节的地方都没有讲到。因此，我打算通过图文配合的方式，总结大佬经验，一步步地实现这个算法。
在反转链表中，迭代和递归都可以用来实现，这里让我们看一下它们之间的区别：
迭代：通过遍历链表并逐步改变指针的指向来实现链表的反转。具体步骤是使用三个指针分别指向当前节点、前一个节点和下一个节点，然后在遍历过程中不断更新这三个指针的指向，直到遍历到链表末尾。
递归：通过“先深入后返回”的策略，首先会一直递归调用自身，直到到达链表的尾部，并在递归的过程中改变节点之间的指向来实现链表的反转。具体步骤是先递归地反转子链表，然后将当前节点的下一个节点的指针指向当前节点，并将当前节点的指针指向空。
总的来说，迭代通常比递归效率更高，因为递归会消耗更多的内存和时间，而且在递归中可能会出现栈溢出的问题。但在函数式编程中，递归显得更加简洁优雅。具体选择哪种方法取决于个人的偏好。
理论难以理解，让我们具体看一下LeetCode上206.反转链表这道题目。
完整的解题代码如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode *cur = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return cur;
}
};
这里让我们先假设一个链表：
按照顺序执行代码，传入链表头结点head = 1并且head->next = 2都不为空，因此if这个语句跳过执行。
接着到ListNode *cur = reverseList(head->next);，按照程序的执行逻辑，只有cur被赋值，这句代码执行完毕之后，才会开始执行后面的head->next->next = head;代码。
然后让我们看一下，reverseList(head->next)怎么执行的，reverseList()就是自身的函数，即值head->next = 2的结点作为新参数进行递归调用。
此时，入参值head = 2，同样不满足if的判断条件，执行下面代码。
那么又到ListNode *cur = reverseList(head->next);了，还是只有cur被赋值，这句代码执行完毕之后，才会开始执行后面的head->next->next = head;代码。
head->next = 3的结点作为新参数进行递归调用。
依次类推，不断地递归调用，直到触发递归终止条件。
这时，head = 5了，head->next = NULL，意味着if语句为true，会执行里面的return head;语句，同时下方的所有代码都不会再执行。
函数reverseList(head = 5)执行结束后，程序便回到了调用它的reverseList(head->next = 5)的位置，其值便理所当然的赋值给了cur。
上面提到，只有cur被赋值，这句代码执行完毕之后，才会开始执行后面的head->next->next = head;代码。
此时，在函数reverseList(head)中head = 4这个结点，cur = 5这个结点。
(head->next)->next = head;，这行代码表示head->next = 5的这个结点的next域指向head = 4这个结点，实现指针的反转操作。
这时候，肯定有人有些迷糊了，怎么head一会等于5这个结点，一会等于4这个结点。你需要利用堆栈的知识去理解，搞清楚到底函数调用时，原本的参数值是什么。
下面看head->next = NULL，意思4这个结点指向空结点，不再指向任何结点了，当然包括5这个结点。于是断开了4和5这两个结点原来的连接，避免形成环。
终于到了函数reverseList(head = 4)最后一句代码return cur。
cur的值，在之前代码中没有修改过，当然还是5这个结点。
此时，程序便回到了reverseList(head = 3)这个函数中，在执行ListNode *cur = reverseList(head->next);代码中，cur的值依然是5这个结点。
重复执行上述相同的步骤，便回到了reverseList(head = 1)，这个梦开始的地方。
所有代码执行完毕，返回cur = 5这个结点，也就是反转后新链表的头结点。