检测单向链表中循环的起始点是一个常见的问题。解决这个问题的方法如下：

步骤1：使用通常的方法来寻找循环。即使用两个指针，一个以单步递增，另一个以两步递增，如果它们在某个时刻相遇，则表示存在循环。

步骤2：固定其中一个指针的位置，并将另一个指针以单步递增的方式移动，计算移动的步数。当它们再次相遇时，步数将给出循环的长度（这与计算循环链表中元素的数量相同）。

步骤3：将两个指针重置为链表的起始位置，将其中一个指针递增循环长度倍数的步数，并开始移动第二个指针。两个指针以单步递增的方式移动，当它们再次相遇时，就是循环的起始点（这与从链表末尾找到第n个元素相同）。

这个解决方法非常简单易懂。在步骤1中，我们使用快慢指针的方法来检测循环，这是一种常见的解决方法。在步骤2中，我们利用快慢指针的相遇点与循环起始点之间的距离与循环的长度之间的关系来计算循环的长度。最后，在步骤3中，我们通过重置指针位置并递增指针来确定循环的起始点。

有人提出了一个简化步骤的方法，即只需在步骤1结束后将其中一个指针重置到链表的起始位置，然后两个指针都以单步递增的方式移动，再次相遇时即为循环的起始点。但是也有人认为步骤2是必要的，因为被重置的指针可能会在另一个指针还在循环中的时候达到循环的起始点。

还某些情况下了一种被称为Floyd算法的解决方法，证明了步骤2和步骤3的开始是不必要的。如果根节点距离循环的起始点有k个步数，那么循环内的碰撞点距离循环的起始点也是k个步数。这些位置是确定的。

我们可以通过以上方法来检测单向链表中循环的起始点。这个问题的解决方法简单且有效，可以帮助我们更好地理解链表的结构和运作原理。

在这段内容中，我们尝试找出链表中是否存在循环。如果存在循环，我们还要找出循环的起始点。为此，我们使用两个指针slowPtr和fastPtr。在第一次检测（检查循环）中，fastPtr每次移动两步，而slowPtr每次只移动一步。

显然，如果链表中存在循环，它们将在某个点相遇（上图中的点7），因为fastPtr指针的速度是另一个指针的两倍。

现在，我们来解决第二个问题，即找到循环的起始点。

假设它们在点7相遇（如上图所示）。然后，slowPtr退出循环并停留在列表的开头，即点1，但fastPtr仍然停留在相遇点（点7）。现在我们比较两个指针的值，如果它们相同，则它就是循环的起始点，否则我们向前移动一步（这里fastPtr也每次移动一步），再次进行比较，直到找到相同的点。

现在有一个问题，如何可能。这里有一个很好的数学证明。

假设：

m => 从列表开始到循环开始的长度（即1-2-3-4）

l => 循环的长度（即4-5-6-7-8-9）

k => 循环开始到相遇点的长度（即4-5-6-7）

slowPtr的总行程= m + p(l) + k

其中p => slowPtr覆盖的循环的次数

fastPtr的总行程= m + q(l) + k

其中q => fastPtr覆盖的循环的次数

由于fastPtr的速度是slowPtr的两倍

因此，

fastPtr的总行程= 2 * slowPtr的总行程

即

m + q(l) + k = 2 * (m + p(l) +k)

或者，m + k = q(l) - p(l)

或者，m + k = (q-p) l

或者，m = (q-p) l - k

所以，

如果slowPtr从列表的开头开始，行程为“m”，它将到达点4（即1-2-3-4）

而

fastPtr从点7开始，行程为“(q-p) l - k”，它将到达点4（即7-8-9-4），

因为“(q-p) l”是一个完整的圆的长度，重复了“(q-p)”次。

更多细节请参考：http://hrishikeshmishra.com/how-to-find-the-starting-point-of-a-loop-in-a-linked-list/

数学证明中有一个小错误。m + q(l) + k = 2 * (m + p(l) + k) => m + k = q(l) - 2 * p(l)

检测单链表中循环的开始

在单链表中检测循环的开始

问题的出现原因：在单链表中检测循环的开始是一个常见的问题，有时可能会出现一个指针在循环中移动而另一个指针在外部移动，导致两个指针最终相遇于循环的某一点。因此，问题是如何确定循环的开始点。

解决方法：通过数学推导和证明可以解决这个问题。假设k是从头节点到循环开始点的步数，m是从头节点到相遇点的步数，n是循环的步数。同时，考虑两个指针P和Q，其中Q的速度是P的两倍。

简单情况：当k < n时，当指针P到达循环开始点（即移动了k步）时，Q已经移动了2k步。因此，当P进入循环时，Q比P领先k步，因此Q现在在开始点之后n-k步。当P从开始点移动到相遇点时，它移动了m-k步。在这段时间内，Q移动了2(m-k)步。但是，由于它们相遇，并且Q开始在开始点之后n-k步，因此有效地有2(m-k) - (n-k)应该等于(m-k)。因此，n = m。

一般情况：假设k = nX + Y，其中Y < n。当指针P到达循环开始点时，Q已经移动了k步，因此Q比P领先k步。但是请注意，k大于n，这意味着Q会多次循环。因此，现在Q在开始点之后n-(k%n)步。当P从开始点移动到相遇点时，它移动了m-k步（因此，相遇点现在在开始点之前(m-k)%n步）。在这段时间内，Q移动了2(m-k)步。但是，由于它们相遇，并且Q开始在开始点之后n-(k%n)步，因此Q的新位置（从开始点计算为'(2(m-k) - (n - k%n))%n'）应该等于P的新位置（从开始点计算为'(m-k)%n'）。因此，m必须是n的倍数。

因此，通过上述的数学证明，可以解决在单链表中检测循环开始点的问题。无论n，m和k的值如何，这个证明都是正确的。