141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

设定两个指针，p2每次走两步，p1每次走一步，最后如果fast遇到空指针则代表图中没有环。由于每个链表的节点只能指向一个节点，如果遇到null则代表肯定不会遇到环。
相反，如果链表中遇到了环，如下面左图所示，利用相对位置的观点，假设p1是静止的,那么p2每次移动都是在向p1走近一步，最终他们一定会在环中的某一点相遇。

拓展问题

1 求环的长度：p1,p2相遇后，保持p2不变，p1继续向前跑，再次相遇即为环的长度。
2 如何找到环的入口：假设环的长度为R，入口在环上的相对位置为0，假设p1到达入口后，又走了X步才与p2相遇
相遇时，p1一共走了$（L+x）$（L+x）步，在环中的相对位置为$（x\%R）$（x%R）
p2一共走了$（2（L+x））$（2（L+x））步，在环中的相对位置为$（(2（L+x）-L)\%R）$（(2（L+x）−L)%R）
在相遇点，有$(2L+2x-L)\%R == x\%R$(2L+2x−L)%R==x%R，即$(L+2x)\%R==x\%R$(L+2x)%R==x%R。根据同余的性质，$（L+x）\%R=0$（L+x）%R=0。

此时为了寻找环的入口，将p1重新指向表头且仍然每次循环都指向后继，p2每次也指向后继。当p1与p2再次相等时，相等点就是环的入口。再次相遇时，假设p1走了m步，p2走了m步，相遇的地点为 $(m-L)\%R == (x+m)\%R ==同余性质(L+x)\%R == 0$(m−L)%R==(x+m)%R==同余性质(L+x)%R==0