下面输入一个很诡异的链表，暂时称它为“变异链表”，如图4—3所示。从图中可以看出此链表的尾部形成了一个环，请实现一个时间和空间上尽可能高效率的算法来判断输入的链表是否为“变异链表”，要求：给出算法的基本设计思想。

admin2014-04-17 112

问题下面输入一个很诡异的链表，暂时称它为“变异链表”，如图4—3所示。从图中可以看出此链表的尾部形成了一个环，请实现一个时间和空间上尽可能高效率的算法来判断输入的链表是否为“变异链表”，要求：

给出算法的基本设计思想。

选项

答案基本设计思想：设置两个指针fast和slow，初始值都指向头结点，slow每次前进一步， fast每次前进两步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。当然，如果某时刻fast或者fast→next为空指针，则为无环链表。可能疑问点：如果有环，为什么两个指针fast和slow必然重合?会不会每次都恰好错过? 提示：因为fast每次走两步，而slow每次走一步，所以它们之间的差距是一步一步缩小的。当slow进入环入E1点后，fast和slow之间的差距将会一步步缩小，如4→3→2→1→0，到0的时候就重合了。其实这是一个追击问题，是一个比较成熟的定理。

解析

转载请注明原文地址:https://kaotiyun.com/show/ulxi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

为了加强对地方的控制，唐太宗根据山川形势，把全国划分成10个()，经常派官员监察地方官吏。

“时方镇缺守帅，稍命文臣权之……又置转运使、通判，为之条禁，文薄渐为精密，由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。

波兰三次被瓜分的时间是()

苏俄实施新经济政策的根本目的是()。

“时方镇缺守帅，稍命文臣权之……又置转运使、通判，为之条禁，文薄渐为精密，由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。

在阿拉伯()统治时期，阿拉伯军队曾与当时中国的唐朝军队发生冲突。

1837年倡导用无机肥料来补充土壤中耗去的化学元素的化学家是()。

现今我国裕固族的祖先是()

荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。

近曲小管是物质重吸收最重要的部位。()

以下各项属于附带认股权证债券筹资的主要优点是()。

东欧剧变和苏联解体标志着()

某老师讲授圆的周长时，还介绍了我国古代数学家祖冲之的突出贡献。同学们不仅学会了知识，也增强了民族自豪感。该老师遵循的教学原则是()。

社会主义核心价值体系的基础是社会主义荣辱观。（）

某宾馆一层客房比二层客房少5间，某旅游团48人，若全安排在第一层，每间。4人，房间不够，每问5人，则有房间住不满；若全安排在第二层，每间3人，房间不够，每间住4人。则有房间住不满。该宾馆一层有客房多少间?

A.ReasonfornaminghurricanesB.WarningofanapproachinghurricaneC.DeadlywomenD.HistoryofnaminghurricanesE.Or

Seekingtoframehisnewadministrationasonewithafirmfocusonclosingthegapbetweenchildrenfromaffluentandpoorfami