【日拱一卒】链表——链表反转(递归解法)资料

本文主要介绍【日拱一卒】链表——链表反转(递归解法)资料 方法和在新技术下所面对的“挑战”,方便大家深入理解【日拱一卒】链表——链表反转(递归解法)资料 过程。本文也将分享【日拱一卒】链表——链表反转(递归解法)资料 所遇到的问题和应对策略,怎么解决怎么做的问题。
通过深入本文可以理解代码原理,进行代码文档的下载,也可以查看相应 Demo 部署效果。

链表反转递归解法

前言

上篇我们主要介绍链表反转的原地反转解法。

除此以外,是否还有其他解法?

当然,今天就来看看链表反转的递归解法。

 

递归

递归,字面意思,有”递“也有”归“

拿我们经常听到的斐波那契数列来说,公式如下

f(n) = f(n-1) + f(n-2); f(1) = 1, f(2) = 1

现在比如求解f(5)的值,按照公式,可以展开为f(5) = f(4) + f(3),如下图所示

【日拱一卒】链表——链表反转(递归解法)

这时候,我们不知道f(3)和f(4)的值,没关系,继续展开,如下图所示

【日拱一卒】链表——链表反转(递归解法)

从图中可以看出,各个节点已经分解到不能再分解,此时的叶子节点都是已知值,f(1)=1,f(2)=2

”递“过程走完了,下面开始”归“

【日拱一卒】链表——链表反转(递归解法)

如上图所示,沿着红色箭头的方向开始回归,最终得到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 } 

  

结合下图

【日拱一卒】链表——链表反转(递归解法)

我们假设此时传入的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)

【日拱一卒】链表——链表反转(递归解法)

5和4的关系是这样,以此类推,4和3,3和2,2和1都是这样递归来的。

这里是比较绕,大概明白这个思想吧。

 

不忘初心

老王:你不好好种地,你以后长大能干什么

小王:学算法

老王:学算法?!你数组、链表、栈、队列、堆、排序、查找都整不明白,你学什么算法

小王:我只学链表反转递归解法

老王:。。。

 

如果您觉得阅读本文对您有帮助,请点一下“推荐”按钮,您的“推荐”将是我最大的写作动力!如果您想持续
【日拱一卒】链表——链表反转(递归解法)资料部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 【日拱一卒】链表——链表反转(递归解法)资料

提供最优质的资源集合

立即查看 了解详情