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

admin2014-04-17 81

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

曹操统一北方的关键战役是()。

系统阐明社会主义初级阶段理论是在()。

南北朝时期，佛教盛行。与此现象无关的是()。

“土木之变”是明与()之间的冲突导致的。

提出行星绕太阳运行为椭圆形轨道的天文学家是()。

论述15世纪以后美洲作物在中国和欧洲的传播及影响。(2013年统考真题)

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

假定有一条通带为100kHz的信道，每路信号的带宽为3．2kHz，各路信号间的防护带宽为0．8kHz。若采用频分多路复用，那么最多可以同时传输()路信号。

—棵二叉树的后序遍历序列为DABEC，中序遍历序列为DFBAC，则先序遍历序列为()。

甲亢患者手术准备不包括

A．肛门反射消失B．足跖屈力减弱C．躅背伸肌力减弱D．踝反射减弱或消退E．外踝附近及足外侧痛、触觉减退马尾神经受压时可能出现

风湿性心脏瓣膜病伴心力衰竭患者，服用地高辛治疗1周，前3天每天服用0．5mg，后4天每天服用0．25mg，现症状、体征均明显改善。心率80次／分，心电图显示ST段呈鱼钩样改变，目前正确的治疗措施应是

口中黏腻不爽，其临床意义是

监理工程师是施工合同文件中授权承担工程监理工作的个人。()

还款的方式不包含()

企业税后利润必须先用于法定盈余公积金和公益金，然后才能用于还贷。()

下列各项中不符合有关增值税纳税地点规定的是()。

我国小麦的主产区是()。

甲、乙两位村民去县城A商店买东西，他们同时从村口出发，甲骑车而乙步行，但他们又同时到达A商店。途中甲休息的时间是乙步行时间的，而乙休息的时间是甲骑车时间的，则甲、乙途中休息的时间比是()。