快慢指针_快慢指针找链表中的环

推导：慢指针进入环后，快指针最多多绕一个圈。

快指针F先进环，慢指针S后进。

假设慢指针进环那一刻快指针差m步能追上（0<= m 环），根据上边结论，两个指针走m次就会相遇了。

因为m 环，所以快指针在慢指针进环那一刻最多比慢指针多绕一个圈。

快指针和慢指针第一次相遇时的节点pq（碰撞点），快指针和慢指针从该点开始继续往前走，再次碰撞时所用的操作数就是环的长度Length_环。

证明:由上边的推导可得，这里的m为Lengh_环。

假设慢指针进入环中时，即连接点p，快指针（q）需要m步才能追上慢指针。

p和q第一次相遇时，碰撞点在pq处。此时，p走到pq时用了m步。

 假设head到p的距离为a，环长度为Length_环，慢指针走了s步，则快指针走了2s步。

从上图可知:

s = a + m

2s = a + m + n * Length_环（n为快指针绕环的圈数）

可得

a = n * Length_环 - m

也就是：若在头结点和相遇结点分别设一指针，同步(单步)前进，则最后一定相遇在环入口结点p。

可根据这个结论来找到入口节点。

找到连接点p后，求head到p的长度，再加上环的长度，即为链表的总长。