检测链表中循环开始的证明
检测链表中循环开始的证明
从stackoverflow和其他地方的几篇帖子中，我了解到如何检测链表中的循环以及循环的长度。我还找到了检测循环开始的方法。以下是参考步骤：
检测循环：
使用两个指针，经典地称为“兔子”和“乌龟”。兔子每次移动2步，乌龟每次移动1步。如果它们在某个点相遇，则肯定存在一个循环，而且相遇点显然在循环内部。
找到循环的长度：
将一个指针固定在相遇点，同时递增另一个指针，直到它们再次相等。在此过程中递增一个计数器，相遇时的计数器值将是循环的长度。
找到循环的开始：
将一个指针指向链表的起始点，将另一个指针保持在相遇点。现在两个指针都每次递增一步，相遇点即为循环的开始。我在纸上验证了这个方法，但我不明白为什么它能够工作。
是否有人能够提供数学证明为什么这个方法有效？
这个问题的出现原因是对于检测链表中循环起始点的证明不够简单明了。作者提出了一种简化证明的方法，即让第二个指针从第一个指针所指向的“相遇点”之后的M个节点（M为循环的长度）开始移动。这样，证明就变得非常明显了。当第一个指针到达循环的起始点时，第二个指针将恰好相距M个节点，也就是在循环的起始点。M不一定等于循环的长度，它可以是循环长度（N）的倍数。这并不会改变任何事情，只是一个技术性的细节，因为在Z mod N中，M仍然等于0。尼基塔将M定义为“循环的长度”，在这种情况下，M肯定等于循环的长度。这个证明可能让你相信算法是正确的，但它并没有证明任何东西。请参考这里的顶部答案，了解如何正确撰写证明。
链表中环的检测是一个常见的问题。我们可以使用两个指针（快指针和慢指针）来检测链表中的环。具体算法如下：
1. 声明两个指针 pFast 和 pSlow。
2. 令 pSlow 和 pFast 都指向链表的头节点。
3. 当 pSlow、pFast 或者两者都指向 NULL 时，重复以下步骤：
- pSlow 前进一步
- pFast 前进两步
- 如果 pSlow 和 pFast 相遇，则说明链表中存在环，停止算法。
4. 如果执行到这一步（即 pSlow 和 pFast 有一个或者两个指针指向 NULL），则说明链表中不存在环。
以上算法中，我们假设该算法是正确的。在该算法中，环的起点被表示为一个特定的节点，其他节点被标记为其目标节点减一的数值。如果一个节点被标记为 i，并且不是环的起点，则它被指向的节点会被标记为 i-1。
该算法可以被描述为一个循环，其中主要步骤（第3步）是一组子步骤，重复执行直到满足退出条件。因此，我们需要根据算法执行的迭代次数 t 来表示 pFast 和 pSlow。
如果链表没有环，指针的位置可以使用 t 来表示：
pSlow = t
pFast = 2t
然而，由于链表中存在环，指针的位置无法简单地用 t 来表示。假设环的起点为 m，环的长度为 n，则当 t=0 时：
pSlow = m
pFast = m
如果根据以上算法描述，一个指针足以检测到链表中的环，那么方程 t(m,n) = t(n,m) 必须存在解。
这个方程成立的条件是 t 存在一个值，使得：
2t - t = kn (k 是一个整数)
这可以简化为：
t = kn
因此，我们可以得出结论：使用一个慢指针和一个快指针足以检测到链表中的环。
但是，这个证明并没有解决如何检测到环的起点的问题。这是一个比较复杂的问题。
链表中检测循环开始的证明的问题是如何检测链表中是否存在循环，并找到循环的起始点。下面是解决这个问题的原因和方法。
假设链表中存在循环，快指针和慢指针在某一点相遇。设慢指针在相遇前走过的距离为x+y，其中x是从链表起点到循环起始点的距离，y是循环的长度。快指针在相遇前走过的距离为(x+y)+y=x+2y+z，其中z是快指针在循环内多余慢指针一圈的距离。
由于快指针的速度是慢指针的两倍，而且它们在相遇时所用的时间是相同的。根据速度、时间和距离的关系，可以得到2(x+y)=x+2y+z，化简得x+z=2x+2y，进一步化简得x=z。
因此，将慢指针移动到链表起点，并使慢指针和快指针每次移动一个节点，它们都需要移动相同的距离。它们将在链表中循环开始的地方相遇。
需要注意的是，这个证明假设它们在一圈后相遇，但实际上快指针可以在慢指针走过距离x时做任意多圈的旋转。因此，这个证明中的图示是过于简化的。