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

admin2014-04-17 72

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

学硕统考专业

根据《国际联盟盟约》的内容分析其实质。

第二次世界大战的爆发是多种因素综合作用的结果，其最根本的原因是()。

继承并发展德谟克利特和伊壁鸠鲁的“原子论”，认为宇宙万物都是由原子构成的，并按照物质本身所特有的规律发展的罗马共和国时期的哲学家()。

1911年，美国工程师()出版《科学管理原理》一书，奠定了科学管理的理论基础，被誉为“科学管理之父”。

对西欧封建社会的说法不正确的是()。

明朝灭亡后，以下南明小朝廷存在的先后顺序是()。①绍武政权②永历政权③隆武政权④弘光政权

“二战”爆发的原因是多种因素综合作用的结果，其中最根本的因素是()。

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

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

指令字长为12位，每个地址码为3位，采用扩展操作码的方式，设计4条三地址指令、16条二地址指令、64条一地址指令和16条零地址指令。(1)给出一种操作码的扩展方案。(2)计算该方案操作码的平均长度。

素质教育的特征具体包括()。

简述随行就市定价法的适用条件。

督脉虚寒，胞脉失煦，引起的妇科疾患，下列不适宜的方剂是

石膏配牛膝属于()黄连配木香属于()

A．肾精不足证B．肾阴虚证C．心血虚证D．血热证E．气血两虚证头发早白，牙齿脱落，足痿无力多见于

下列各项中，影响年末未分配利润数额的因素有(。)。

为最大限度提高资金效益、简化结存手续，银行应根据()等规定管理旅行社质量保证金。

假如你进入监狱工作后，组织监狱干警对青海玉树灾区的募捐活动，但当你最后清点时却发现少了一包衣物和1000元现金。你会采取什么措施?

(41)能最准确地计算活动的历时(AD)。