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

admin2014-04-17 41

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

反映查理大帝进攻阿拉伯人控制的西班牙的文学作品是()。

解放战争中，促使中共进行战略决战的重要因素是()。

戊戌政变发生的时间是()。

光绪皇帝颁布“明定国是”诏书的时间是()。

在阿拉伯()统治时期，阿拉伯军队曾与当时中国的唐朝军队发生冲突。

试结合新民主主义革命不同历史时期的历史实际，阐述中国共产党在处理同资产阶级复杂关系问题上的做法、结果及其历史经验。

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

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

晚清时期清帝年号的正确排序是()

什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?

预防中枢神经系统白血病时，常用作鞘内注射的化疗药是

A．生理需要B．安全需要C．爱与被爱的需要D．尊重的需要E．自我实现的需要发挥自己的潜能，实现自已的理想与抱负的需要是

患者，男，50岁，失眠症数年。关于其治疗与护理措施正确的是()

按照病理分类，婴幼儿最常见的肺炎是

流动资产是指预计在一个正常营业周期中变现、出售或耗用的资产。()

教师：教室正确选项为()

为保证满负荷，必须有多高的出勤率?如果该厂段优化组合掉20人，又要保护90%的出勤率，必须提高多少效率?

在FastEthernet中，为了使物理层在实现100Mbps速率时所使用的传输介质和信号编码方式的变化不会影响MAC子层，100BASE-T标准定义了______。

Readthefollowingpassageandfillintheblankswithitscontents.WritethemonyourANSWERSHEET.Asperthetermsandc

A、Byteachingwritershowtoimitate.B、Byidentifyingwriter’sstrengthandweakness.C、Bydevelopingwriter’spotential.D、By