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

admin2014-04-17 29

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

简述近代香港问题的形成。

洋务派创办的第一个规模较大的近代军事工业企业是()。

斯大林模式的突出特点是()。

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

从1939年春天起，国共双方军队在驻防结合部的摩擦冲突不断升级，不是这一时期惨案的是()

中国历史上第一部资产阶级革命法典《临时约法》公布的时间是()。

下列选项中，控制了西域政权的是()

西南军阀跟随孙中山拥护护法运动的目的是()。

商族的远祖可追溯到尧舜时代的契，传说契母简狄吞玄鸟之卵而生契。契便是商人的祖先。以此传说推测，商族是以()为图腾的部落。

明末清初，著名学者()抗清失败，前往日本讲学，传播中国文化。

PowerPoint2010系统默认的视图方式是幻灯片视图。

脑部基底节出血的典型表现是（）

依据《中华人民共和国药品管理法》，下列情形按假药论处的是

期间核查是由本实验室人员使用自己选定的核查标准按照_________进行。

烧结普通砖砌体砌筑方法中的“三一”砌砖法是指()。

一些设备报废后,只存在可回收利用金属的价值,称为()。

在事先确定企业资金规模的前提下，吸收一定比例的负债资金，可能产生的结果是()。

某有限责任公司设立监事会，根据我国公司法，该公司监事会成员不得少于()。

设z=f(x，y)由方程z—y—x+xez－y－x=0确定，求dz．