检测链表循环开始的证明 [英] Proof of detecting the start of cycle in linked list

问题描述

从stackoverflow内部和外部的几个帖子中，我已经知道如何检测链表中的循环，循环的长度.我还找到了如何检测循环开始的方法.

From several posts inside stackoverflow and outside, I have come to know how to detect cycles in a linked list, the length of a cycle. I also found the method on how to detect the start of the loop.

这里再次提供步骤以供参考.

Here are the steps again for reference.

检测循环:

有两个指针，传统上称为兔子和乌龟.兔子走2步，乌龟走1步.如果它们在某个点相遇，那么肯定有一个循环，并且相遇点显然在循环内.

Have two pointers, classically called hare and tortoise. Move hare by 2 steps and tortoise by 1. If they meet at some point, then there is surely a cycle and the meeting point is obviously inside the cycle.

求循环长度:

保持一个指针固定在汇合点，同时增加另一个直到它们再次相同.继续增加一个计数器，相遇时的计数器值将是周期的长度.

Keep one pointer fixed at meeting point while increment the other until they are same again. Increment a counter as you go along and the counter value at meet will be the length of cycle.

找到循环的开始

将一个指针指向列表的开头，并将另一个指针放在会合点.现在加一，交汇点是循环的开始.我在纸上使用一些案例验证了该方法，但我不明白为什么它应该有效.

Take one pointer to start of the list and keep the other at the meeting point. Now increment both by one and the meet point is the start of loop. I verified the method using some cases on paper, but I don't understand why it should work.

有人能提供一个数学证明来说明为什么这种方法有效吗?

Can someone, provide a mathematical proof as to why this method works?

推荐答案

如果您不使用会合点，您可以使您的找到循环的开始"证明更简单.
让第二个指针不是从交汇点"开始，而是 M 领先于第一个指针.(其中 M 是循环的长度.)

You can make your 'Find the start of cycle' proof simpler if you don't use meeting point.
Let second pointer start not at the 'meeting point', but M steps ahead of first pointer. (Where M is the length of the loop.)

这样，证据就很明显了.当第一个指针到达循环开始时，第二个指针将提前 M 步:也在循环的开始.

This way, proof is pretty obvious. When the first pointer reaches start of the loop, second will be exactly M steps ahead: also at the start of the loop.

这篇关于检测链表循环开始的证明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！