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

admin2014-04-17 73

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

学硕统考专业

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

科举是一种读书、应考、任官三位一体的选官方法，其中的进士科始创于()。

1925年10月签订《洛迦诺公约》后，法国外长白里安认为：“我国的安全比以往任何时候都更有保障了。”对此说法不正确的一项是()。

下列著作不属于被后世称为清代汉学的“不祧祖先”之人的作品的是()

下列选项中，不是由晁错提出的是()

重庆谈判的焦点问题是()

文艺复兴时期，系统提出了国家主权理论的政治思想家是()。

简述清代秘密立储制的操作并作出评价。

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

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

机关、团体为达到某一目标或完成某一任务之前所制定的时段工作的设计和安排的文书称为()

A．遗传性球形红细胞增多症B．遗传性椭圆形红细胞增多症C．丙酮酸激酶缺乏D．珠蛋白生成障碍性贫血脾切除可减轻溶血、减少输血量的疾病是

诸多因素使我国的利率期限结构表现出不同的层次,以法定利率表为基础形成利率的期限结构属于()

人力资本水平既定的某位员工，在不同的时间或不同工作环境中可能会表现出不同的生产率，这种生产率变化的主要影响因素是()。

宏观经济调控的手段主要包括()。

货币供给之所以是内生变量，是因为货币当局能够对货币乘数实施直接或完全的控制。()

唱名法分为()。

OnlineHealthForumTherearemanyaspectstohealth,illnessandhealing./Amongalltheteachingsthereisonethemethat