内容简介:上篇我们主要介绍链表反转的原地反转解法。除此以外,是否还有其他解法?当然,今天就来看看链表反转的递归解法。
前言
上篇我们主要介绍链表反转的原地反转解法。
除此以外,是否还有其他解法?
当然,今天就来看看链表反转的递归解法。
递归
递归,字面意思,有”递“也有”归“
拿我们经常听到的斐波那契数列来说,公式如下
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都是这样递归来的。
这里是比较绕,大概明白这个思想吧。
不忘初心
老王:你不好好种地,你以后长大能干什么
小王:学算法
老王:学算法?!你数组、链表、栈、队列、堆、 排序 、查找都整不明白,你学什么算法
小王:我只学链表反转递归解法
老王:。。。
如果您觉得阅读本文对您有帮助,请点一下“ 推荐 ”按钮,您的 “推荐” 将是我最大的写作动力!如果您想持续关注我的文章,请扫描二维码,关注JackieZheng的微信公众号,我会将我的文章推送给您,并和您一起分享我日常阅读过的优质文章。
<em><img src="https://images0.cnblogs.com/blog2015/619240/201505/162205410643708.jpg" alt="" /></em>
以上所述就是小编给大家介绍的《【日拱一卒】链表——链表反转(递归解法)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 欣赏一个简洁利落的解法
- 欣赏一个简洁利落的解法
- Script error 问题解法
- 一道SQL题的多种解法
- Leetcode 139. WordBreak 解法和思路
- 怎么推导《最大子序和》的动态规划解法
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
机器与人:埃森哲论新人工智能
【美】保罗•多尔蒂 詹姆斯•威尔逊 / 赵亚男 / 中信出版社 / 2018-10-1 / 49.00元
自人工智能问世以来,人们普遍持有人机对立的观点,且无时无刻不在害怕自己的工作会被人工智能取代。作者认为,是时候抛开这些无谓的担忧了,因为人类社会正走向一个与机器共融共生的时代。 未来的新型工作模式是什么?未来有哪些工作不会被人工智能取代?人工智能时代重要的生存技能是什么?本书围绕这三大核心问题做了透彻的分析。作者带我们见识了置于业务流程背景之下的人工智能,阐述了其在不同职能部门中起到的推动作......一起来看看 《机器与人:埃森哲论新人工智能》 这本书的介绍吧!