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

admin2014-04-17 39

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

李鸿章奏请在天津设立的北洋水师学堂的落成时间是()。

八路军建立的第一个敌后抗日民主根据地是()。

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

1951年底到1952年春，中国共产党在党政机构工作人员中开展的运动是()。

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

美国主张建立国际联盟的主要目的是()。

在巴黎和会上，法国要求严厉制裁德国的目的是()。

若有4个进程共享同一程序段，每次允许3个进程进入该程序段，用P、V操作作为同步机制，则信号量S的取值范围是()。

简述审美理想与人生理想的内在关联。

试述在真理问题上实践标准的辩证法，并用这一原理说明坚持解放思想、实事求是思想路线的重要性。

病毒感染时中性粒细胞碱性磷酸酶(NAP)积分值

下列药物主归膀胱经的是

没有风险和通货膨胀情况下的平均利率是()。

Withinjustsixweeksofthesafetyprogram’s______,on-the-jobaccidentshaddroppedbyalmost30%.

求不定积分。

在教育教学中，应针对学生的气质差异，因材施教。下列四种气质类型的学生犯了错误，其中做法正确的是()

在文化事业单位的主要类别中，下列属于群众文化事业单位的有（）。

卡尔森以前只有宾馆管理经验而无航运业管理经验，但在他被聘为美国泛美航空公司的总裁后，短短三年，就使这家亏本企业成为高盈利企业。你认为下述四条说法中有明显的错误。