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

admin2014-04-17 96

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

学硕统考专业

1948年，南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法，其核心是()。

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

在下列我国建国之后的外交活动中，能够体现“和而不同”思想的有()①亚非会议主张“求同存异”②提出“和平共处五项原则”③中日关系实现正常化④同第三世界国家建立友谊

国民党的第一次代表大会上通过的《中国国民党第一次全国代表大会宣言》，其内容不包括()

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

简述弭兵之会的背景、过程和结果。

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

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

进程P0和P1的共享变量定义及其初值为：booleanflag[2]：intturn=0：flag[0]=FALSE；flag[1]=FALSE；若进程P0和P1访问临界资源的类C伪代码实现如下：则并发执行进程P0和P1时产生的情形是____。

Word2010中，嵌入式图片只要转化成浮动式的，也可以进行图形组合。()

统计工作中最关键的一步是()

甘麦大枣汤的主治病证是

基本预备费是预留的以应付在项目实施中难以预料的支出的费用，其计算以()为基础。

施工质量控制的共同性依据包括()。

公安机关是人民民主专政的工具,这是公安机关的阶级属性,也是它的根本属性。()

左边是给定的纸盒的外表面，下列哪一项能由它折叠而成？

刑法第151条第4款规定：“犯第1款、第2款罪，情节特别严重的，处无期徒刑或者死刑，并处没收财产。”本规定的罪状属于（）。

假设X=100，则函数IIF(X＜50，X-50，X+50＝的值为　【】　。

计算机408

学硕统考专业

1948年，南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法，其核心是()。

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

在下列我国建国之后的外交活动中，能够体现“和而不同”思想的有()①亚非会议主张“求同存异”②提出“和平共处五项原则”③中日关系实现正常化④同第三世界国家建立友谊

国民党的第一次代表大会上通过的《中国国民党第一次全国代表大会宣言》，其内容不包括()

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

简述弭兵之会的背景、过程和结果。

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

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

进程P0和P1的共享变量定义及其初值为：booleanflag[2]：intturn=0：flag[0]=FALSE；flag[1]=FALSE；若进程P0和P1访问临界资源的类C伪代码实现如下：则并发执行进程P0和P1时产生的情形是____。

Word2010中，嵌入式图片只要转化成浮动式的，也可以进行图形组合。()

统计工作中最关键的一步是()

甘麦大枣汤的主治病证是

基本预备费是预留的以应付在项目实施中难以预料的支出的费用，其计算以()为基础。

施工质量控制的共同性依据包括()。

公安机关是人民民主专政的工具,这是公安机关的阶级属性,也是它的根本属性。()

左边是给定的纸盒的外表面，下列哪一项能由它折叠而成？

刑法第151条第4款规定：“犯第1款、第2款罪，情节特别严重的，处无期徒刑或者死刑，并处没收财产。”本规定的罪状属于（）。

假设X=100，则函数IIF(X＜50，X-50，X+50＝的值为 【】 。

假设X=100，则函数IIF(X＜50，X-50，X+50＝的值为　【】　。