欧博app下载:【日拱一卒】链表——链表反转(递归解法)

admin 3个月前 (07-02) 科技 34 0

前言

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

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

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

 

递归

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

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

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
}

  

连系下图

欧博app下载:【日拱一卒】链表——链表反转(递归解法) 第1张

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

欧博app下载:【日拱一卒】链表——链表反转(递归解法) 第2张

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

这里是对照绕,也许明了这个头脑吧。

 

不忘初心

老王:你不好好种地,你以后长大醒目什么

小王:学算法

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

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

老王:。。。

 

若是您以为阅读本文对您有辅助,请点一下“推荐”按钮,您的“推荐”将是我最大的写作动力!若是您想连续关注我的文章,请扫描二维码,关注JackieZheng的微信民众号,我会将我的文章推送给您,并和您一起分享我一样平常阅读过的优质文章。

欧博app下载:【日拱一卒】链表——链表反转(递归解法) 第3张
,

AllbetGmaing客户端下载

欢迎进入AllbetGmaing客户端下载(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

Sunbet声明:该文看法仅代表作者自己,与本平台无关。转载请注明:欧博app下载:【日拱一卒】链表——链表反转(递归解法)

网友评论

  • (*)

最新评论

文章归档

站点信息

  • 文章总数:642
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1010
  • 评论总数:267
  • 浏览总数:7544