前言
上篇我们主要介绍链表反转的原地反转解法。
除此以外，是否还有其他解法？
当然，今天就来看看链表反转的递归解法。
递归
递归，字面意思，有”递“也有”归“
拿我们经常听到的斐波那契数列来说，公式如下
f(n) = f(n-1) + f(n-2); f(1) = 1, f(2) = 1
现在比如求解f(5)的值，按照公式，可以展开为f(5) = f(4) + f(3)，如下图所示
image.png
这时候，我们不知道f(3)和f(4)的值，没关系，继续展开，如下图所示
image.png
从图中可以看出，各个节点已经分解到不能再分解，此时的叶子节点都是已知值，f(1)=1,f(2)=2
”递“过程走完了，下面开始”归“
image.png
如上图所示，沿着红色箭头的方向开始回归，最终得到f(5)的值为8
如上就是递归的过程，从下面的代码层面，我们可以看到底层的表示形式就是自己调用自己，直到满足阈值条件则停止。
递归反转链表
先上代码
func reverse(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
newHead := reverse(head.Next)
head.Next.Next = head
head.Next = nil
return newHead
}
结合下图
image.png
我们假设此时传入的head指向的是带反转的链表，目前head的值为5。
既然这里用到了递归的思想，那么这里
newHead := reverse(head.Next)
head.Next即为4，我们拿到的newHead此时就是一个已经完成反转的链表了，这是目前还差5这个节点。
下面只要将4指向5，再让5的Next指向nil，就是一个完整的反转链表了。
head.Next.Next = head即表示4指向5（head.Next为4，head为5）
head.Next = nil（5的下一个节点即head.Next）
image.png
5和4的关系是这样，以此类推，4和3，3和2，2和1都是这样递归来的。
这里是比较绕，大概明白这个思想吧。
不忘初心
老王：你不好好种地，你以后长大能干什么
小王：学算法
老王：学算法？！你数组、链表、栈、队列、堆、排序、查找都整不明白，你学什么算法
小王：我只学链表反转递归解法
老王：。。。
网友评论