快慢指针判断单链表是否有环证明问题。_判断单链表是否有环 快慢指针 证明

1.判断单链表是否有环：
使用快慢指针fast和slow，fast每次走两步，slow每次走一步，如果有环，肯定会相遇，如果没有，则指针fast遇到NULL退出。追及相遇问题。
2.求有环单链表的环长
在环上相遇后，记录第一次相遇点为Pos，之后指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。
设从第一次相遇到第二次相遇，设slow走了len步，则fast走了2*len步，相遇时多走了一圈：

环长=2*len-len

3.求有环单链表的环连接点位置

也就是A的位置是头节点，B表示环入口处，C表示快慢指针第一次相遇处。 在C处相遇时，设慢指针跑了N步，也就是从A开始N步后会到达C。

快指针比慢指针走的快一倍，也就是走了2*N步。那么慢指针从C处再跑N步还会回到C处。 既然都会回到C处，那么必然会在B点第一次相遇。
所以我们在入口处再设一指针(用之前快指针即可)，与慢指针用1步长同时前进，第一次相遇处就是环入口处

第一次碰撞点Pos到连接点Join的距离=头指针到连接点Join的距离，因此，分别从第一次碰撞点Pos、头指针head开始走，