检测链表中循环开始的证明
Sha*_*fiz 31 algorithm linked-list
从stackoverflow和outside里面的几个帖子中,我已经知道如何检测链表中的循环,循环的长度.我还找到了如何检测循环开始的方法.
以下是再次参考的步骤.
检测循环:
有两个指针,通常称为野兔和乌龟.将野兔移动2步并将龟移动1.如果它们在某个时刻相遇,那么肯定会有一个循环,并且会合点显然在循环内.
寻找循环的长度:
保持一个指针固定在会合点,同时增加另一个,直到它们再次相同.随着时间的推移增加一个计数器,满足时的计数器值将是循环的长度.
找到循环的开始
取一个指针开始列表,另一个指向会合点.现在将两者递增,并且满足点是循环的开始.我在纸上使用了一些案例验证了这种方法,但我不明白为什么它应该起作用.
有人可以提供一个数学证明,说明为什么这种方法有效吗？
Pab*_*lgo 48
如果通过指向其第一个节点(列表)的指针表示列表
检测环路的算法描述如下:
- 声明两个指针(pFast)和(pSlow).
- 使pSlow和pFast指向列表.
- 直到(pSlow),(pFast)或两者都指向NULL:
- 如果
,然后刚刚找到STOP作为循环.
- 如果已达到此点(一个或两个指针都为NULL),则列表中没有循环.
让我们假设这个算法是正确的.在此方案中,循环情况由下图表示:
注意除了指向循环开始的节点之外,每个节点如何标记其目标数减1.因此,如果一个节点用i标记并且它不是循环的开始,那么它被标记为i-1的节点指向下一个元素.
上面解释的算法可以被描述为循环,因为其主要步骤(3)是一组子步骤,其重复直到满足退出条件.这迫使我们在算法执行(t)中代表迭代次数的pFast和pSlow.
如果列表没有循环,则指针位置将在t的函数中描述为:
然而,有一个循环开始的节点,该函数停止描述指针的演变.假设这个指针用m标记,那么循环包含节点(即
和 
),并将t = 0设置为迭代值时
然后:
如果一个指针确实足以使用所描述的算法检测循环,则它必须至少存在方程的解 
.
当且仅当存在t的值时,该等式才成立:
这以一个函数结束,
生成t的值,它们是上述等式的有效解:
因此,证明了一个慢指针和一个快速指针足以检测链表中的循环条件.
- 非常好的正式证明!我希望有一个SO功能,其中最高评级的答案将弹出顶部,然后接受答案. (4认同)
- 为什么乳胶渲染不正确？ (3认同)
- 你是对的，这与黑暗模式有关。切换到灯光模式并点赞 (3认同)
Nik*_*bak 20
如果不使用会合点,可以使"查找循环开始"证明更简单.
让第二个指针不在"会合点"开始,而是M在第一个指针之前步进.(M循环的长度在哪里.)
这样,证据非常明显.当第一个指针到达循环的开始时,第二个指针将正好M向前迈进:也就是在循环开始时.
- “ M”不一定等于循环长度，它可以是循环长度（“ N”）的倍数。（这不会改变任何东西，只是一个技术上的问题，因为“ Z mod N”中的“ M”仍然等于0。）+1 (3认同)
- 我很高兴这个“证明”让你相信算法是正确的，但它根本不能证明任何事情。请参阅此处的最佳答案，了解如何正确编写证明。-1 来自我。 (2认同)
小智 10
在meeting = x + y之前slowPointer行进的距离
fastPointer在会议之前行进的距离=(x + y + z)+ y = x + 2y + z
由于fastPointer的行进速度是slowPointer的两倍,因此当到达会合点时,两者的时间都是恒定的.
所以通过使用简单的速度,时间和距离关系2(x + y)= x + 2y + z => x + 2y + z = 2x + 2y => x = z
因此,通过将slowPointer移动到链接列表的开始,并使slowPointer和fastPointer一次移动一个节点,它们都具有相同的距离.
它们将在链接列表中的循环开始点到达.
- 谨慎从您使用此处获得信用？:) (12认同)
- 为什么假设他们会在一次轮换后见面？ (4认同)
- 这张图过于简化了。因为快指针总是比慢指针快两倍，所以当慢指针移动距离 x 时，快指针可以绕循环进行任意次数的旋转。 (4认同)