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

admin2014-04-17 110

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

学硕统考专业

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

新石器时代的房屋建筑根据环境的不同形成了不同的类型，()地区多为干栏式建筑。

明长城的起止地点是()。

1991年，南斯拉夫联邦解体，分裂为新国家的数目为()。

克里特文明的文字类型是()。

列宁在()中系统地阐明了马克思主义的国家学说。

我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。

葡萄牙、西班牙最早走上殖民征服道路，从政治上来说是由于()

1901年6月，发表《立宪法议》，首先提出君主立宪要求的是()。

中国共产党在敌后战场上开创的第一块根据地是()。

硬下疳(chancer)

A．对硫磷B．氯硫磷C．氧乐果D．敌敌畏E．敌百虫有机磷杀虫药中属于中毒类的是

触摸屏通过________方式与可编程序控制器交流信息。

张力性气胸致死的主要原因是（）。

某郊区学校为方便乘坐地铁，与相邻研究院约定，学校人员有权借研究院道路通行，每年支付1万元。据此，学校享有下列哪一项权利?()

水利水电工程编制施工总进度应遵循的原则是()。

金属风管的材料品种、规格、性能与厚度等应符合设计和现行国家产品标准的规定，下列金属风管的制作和连接中不符合要求的是()。

从问题的提出、方案的设计到实施以及结论的得出，完全由学生自己来做，重研究过程甚于注重结论，这种课程是__________课程。

人民行使国家权力的机关是全国人民代表大会。()

A．大家B．张C．除了D．几E．变化F．客气A：葡萄()块钱一斤?B：3块，多买可以便宜一点儿。