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

admin2014-04-17 40

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

学硕统考专业

蒙古军西征之后，罗斯处于()的控制之下。

《吕氏春秋》载：“公作则迟，有所匿其力也；分地则速，无所匿其力也。”这条材料反映的实质问题是()。

维也纳会议争论的焦点问题是()。

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

1936年，张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成

评析郑和下西洋的历史条件和意义。

开皇五年，文帝规定每年正月五日县令出查，令百姓五党三党为一团，根据标准定户等上下，从轻制定税额，并将各户应纳税额写成定簿，是为()。

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

1945年，联合国成立之时，创始会员国共有()个国家。

Borntrager反应呈阳性的是()

在国际上，采用固定总价合同，在业主和承包商都无法预测风险的条件下和可能有工程变更的情况下，（）。

甲公司以出包方式建造厂房，建造过程中发生的下列支出中，应计入所建造厂房成本的有()。(2014年)

在我国兰州一昆明一线以西，绝大部分山地为高山和极高山，下列超过8000米的高峰有()。

2015年3月15日，第十二届全国人民代表大会第三次会议表达通过了修改《中华人民共和国____________法》的决定。这是该法自2000年实施以来的第一次大修。

“三个代表”要求，是我们党保持先进性，始终成为建设有中国特色社会主义坚强领导核心的()。

动作技能形成中的特征变化有()

有以下程序：#include＜stdio．h＞main(){inty=9；for(；y＞0；y——)if(y％3==0)printf(＂％d＂，——y)；}程序的运行结果是()。