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

admin2014-04-17 56

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

说明你所设计算法的时间复杂度和空间复杂度。

选项

答案空间复杂度分析：除去链表本身外，只有O(1)的空间消耗。时间复杂度分析：如果链表无环，那么经过n／2步之后，fast会走到链表的末端，程序结束。如果链表有环，假设经过k步之后slow进入环中(k＜n)，此时slow和fast之间的距离为m(m＜n)。由于fast每次比slow多走一步，那么经过m步之后，fast就会恰好追上slow。两步的时间复杂度均为O(n)，所以总的时间复杂度也是O(n)。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

唐朝时，从中国传到大食的手工技术是()

永元四年(公元92年)，汉和帝用宦官()掌握的一部分禁军，消灭了窦氏势力。郑众从此参与预政事，并受封为侯，这是宦官用权和封侯的开始。

建立中国道教史上第一个成熟的神仙系统的是()。

洋务运动中翻译出《几何原本》后九卷、《代数学》、《重学》等数学、物理方面的科技书籍的翻译家是()。

明代中后期，随着工商业的发展和南北经济联系的加强，在江南地区，自宋元以来初露端倪的新的城市类型——()得到很快的发展。

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

第一国际成立前，各国无产阶级强烈要求加强国际团结的直接原因是()。

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

编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。

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

A、Peoplemaintaintheharmonybetweenthehumanandtheearth.B、Peopleintheglobalvillagedosomethingtostopicefrommelt

cAMP能变构激活

A．低渗性脱水B．高渗性脱水C．等渗性脱水D．低钾血症E．代谢性酸中毒一患者腹泻10天，出现极度烦渴、高热、尿少、尿比重高，血清钠160mmol／／L，诊断为()

男，44岁。刷牙时牙龈出血10年，检查见牙石(＋＋)。菌斑量多．牙龈红肿明显，探诊出血，袋深普遍4～6mm，附着丧失普遍2～4mm。X线片示牙槽骨有水平吸收。最可能的诊断是

下列账户中，在会计期末一定没有余额的有()。

某农村家庭的调查显示，电冰箱拥有率为49％，电视机拥有率为85％，洗衣机拥有率为44％，至少有两种电器的占63％，三种电器齐全的占25％，则一种电器都没有的比例为()。

我在繁忙的工作之余，时常拿起相机，游走于城市的大街小巷，去探寻城市中那些_________的古迹和古迹后面那些有韵味的老故事。填入画横线部分最恰当的一项是（）。

OfallthecatastrophesthatcouldbefallAmericaincomingyears,abigterroristattack,perhapsevenbiggerthanthoseonSep

Someonewhoishurtbadlyandisunconscious______pain.Whichofthefollowingistrue?

•Readthetextbelowabouttelevisionnetwork.•Inmostofthelines(41-52)thereisoneextraword.Itiseithergrammatica