栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

使用Hare and Tortoise方法在链表中进行循环检测

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

使用Hare and Tortoise方法在链表中进行循环检测

这是一个非正式证明的尝试。

周期的形状无关紧要。它可以有一条长长的尾巴,并有一个向尾的循环,或者只是从头到尾的循环而没有尾巴。不管周期的形状如何,很明显-
乌龟指针无法追赶野兔指针。如果两者碰面,野兔指针必须从后面追赶乌龟指针。

建立了这种可能性后,请考虑以下两种可能性:

  1. 野兔指针比乌龟指针落后一步。
  2. 野兔指针比乌龟指针落后两步。

所有更大的距离最终将减少到一两个。

假设乌龟指针始终先移动(也可以相反),然后在第一种情况下,乌龟指针向前移动一步。现在它们之间的距离为2。当野兔指针现在走2步时,它们将降落在同一节点上。这是为便于理解而说明的同一件事。太多的文字会挡住。

♛=野兔♙=乌龟X =都满足..♛♙...#1-最初,野兔距离乌龟仅一步之遥。..♛.♙..#2-现在乌龟迈出了一步。现在野兔落后了两步。.... X ..#3-接下来,野兔走了两步,他们见了面!

现在让我们考虑第二种情况,它们之间的距离为2。慢速指针向前移动一步,它们之间的距离变为3。接下来,快速指针向前移动两步,它们之间的距离减小为1,等于我们已经证明他们将再进一步一步的第一个案例。再次说明,以便于理解。

.♛.♙...#1-最初,兔子在乌龟后面两步。.♛..♙..#2-现在,乌龟走了一步,彼此分开了三步。...♛♙..#3-接下来,野兔分两个步骤进行操作,与之前的情况相同。

现在,关于为什么保证该算法在O(n)中的原因,请使用我们已经确定的野兔在前进之前
遇到它的原因。这意味着一旦两者都进入循环中,在乌龟完成另一回合之前,它将遇到野兔,因为野兔的移动速度快两倍。在最坏的情况下,循环将是一个具有n个节点的圆。乌龟只可以n步完成一轮,而野兔在那段时间内可以完成两轮。即使野兔在第一个回合中错过了乌龟(也将会),它也肯定会在第二回合中赶上乌龟。



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/617018.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号