博客

首先我们让fast指针（一次走两步）和slow指针（一次走一步）同时指向头结点， 然后同时向后移动。

1. 如果链表是一个整环的话， slow指针走一圈的时候与fast指针重合， 此时fast走了两圈。
   
2. 如果链表不是一个整环， slow指针没来得及走一圈就会与fast指针重合， 此时fast指针比slow指针多走了n圈（n>=1）

假设两个指针第一次重合， slow走了S， fast就走了2S, 设圈长为r

2S = S + nr

S = nr

假设链表长度为L， 头结点到循环起点距离为a，第一次重合slow走的距离为x， 则有

a + x = S = nr = (n – 1)r + r = (n-1)r + L – a

所以a = (n-1)r + L – a – x

L – a – x 刚好是第一次重合点距离起点的距离，

此时我们让其中slow指针指向起点， fast指针不动， 然后两个指针每次都移动一步， 当slow指针移动a次指向循环起点时， fast指针移动了n-1圈加L – a – x， 刚好也指向循环起点， 因此我们就找到了链表循环的起点。