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

admin2014-04-17 95

问题下面输入一个很诡异的链表，暂时称它为“变异链表”，如图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://www.kaotiyun.com/show/ulxi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

第二次世界大战的爆发是多种因素综合作用的结果，其最根本的原因是()。

北魏建立和统一的时间分别是()。

汉武帝时，为太常博士的弟子兴建学校，名为()，学生入学后免除本人的徭役，学成经考试后，

我国第一部系统的史学理论著作是()。

一战后，凡尔赛条约规定了国际联盟管理15年的德国地区是()

1895年发现X射线，拉开物理学革命序幕的科学家是()。

电子计算机的发展经过了四代，①电子数值积分计算机(ENIAC)；②集成电路计算机；③大规模集成电路计算机；④晶体管计算机；⑤人工智能计算机，其先后顺序是()。

第三世界所共有的特征及崛起的标志是什么?

在巴黎和会上，法国要求严厉制裁德国的目的是()。

二战后世界经济走向统一的过程中，仍然存在着多样性，出现了“两种体系、三种国家”，下列不属于社会主义国家经济类型的是()。

不减慢Vmax，稍减慢传导，缩短动作电位时间明显减漫Vmax，显著减慢传导，轻微延长动作电位时间

A．普萘洛尔B．维拉帕米C．硝酸甘油D．可乐定E．硝苯地平稳定型和不稳定型心绞痛都可选用()

水环境点源调查的基本内容包括()。

风险对策研究应在项目决策分析与评价中的()进行。

在导游过程中可能因工作失误或意想不到的事情，造成游客不悦甚至不满，此时导游员首先要想到的是如何()。

某健康人肾动脉血浆和肾小囊中液体的部分成分含量如下表所示：由数据分析可知，几乎不可能通过肾小球和肾小囊壁的是()。

家在梦中何日到，______?

ThetextmainlytellsusaboutWhichofthefollowingisTRUEaccordingtopara.5?

A.approachingB.distinguishC.patternsD.collectE.graspF.managedG.identicalH.rememberedI.exceedingJ.suggeste

Itwasvery(consider)______ofyoutosendmeabirthdaycard.