快慢指针和链表的环

相信用快慢指针确定链表是否有环大家并不陌生，但是如何确定这个链表环起点的位置是一个问题。

为了深入了解，我画了个图方便理解。

下图表示了快慢指针的流程，现在假设（有环）：

快慢指针都从起点B开始，快慢指针最终相交于点C，环的起点位于S。

我们假设慢指针走了 k 的距离，那么快指针走了 2k 的距离，其中(0<k<2k<n)，设 SC 的距离为m，注意是顺时针（S到C）的距离，那么：

 

 可知，BS的距离为 k-m，我们现在 CS 的距离未知，我们假设其为 x，现在来求解x

我们知道快指针走了 2k 的距离是吧，也就是 BS + SC + CS +SC = 2k

那么， k-m + m + x + m = 2k;　　可知 x = k-m，好像发现了不得了的事情！！！，CS和BS距离是一样的！！！

我们通过快慢指针确定了交点C后，只要让快指针指向B，速度设置为和慢指针一样为1，让慢指针从C开始，一起走，只要他们相遇，就一定是在环起点S相遇。CS = BS = k-m

 

因此，快慢指针确定环起点的结论就是，让快指针变成慢指针从起点开始，让慢指针从交点开始，一起走，相遇的点就是环的起点。