Check whether there is a cycle in the linked list(检查链表里是否有环).

Set two pointers(fast, slow) both points the head of the linked list. The slow pointer moves one step, and the fast pointer moves two steps. If there is a cycle, the fast pointer will meet the slow pointer. The program is as follows:



How to find out the entrance of the cycle?

If we found the cycle in the linked list, we let p2 come back to the head of the linked list and go ahead, however, the length of the step should be one. When the meet with P1 and P2, that is the entrance of the cycle.

Chinese Prove:
在p2和p1第一次相遇的时候，假定p1走了n步骤，环路的入口是在p步的时候经过的，那么有

p1走的路径： p+c ＝ n； c为p1和p2相交点，距离环路入口的距离

p2走的路径： p+c+k*L = 2*n； L为环路的周长，k是整数

显然，如果从p+c点开始，p1再走n步骤（即k*L步，p1又循环了k圈）的话，还可以回到p+c这个点

同时p2从头开始走的话，经过n步，也会达到p+c这点

显然在这个步骤当中p1和p2只有前p步骤走的路径不同，所以当p1和p2再次重合的时候，必然是在链表的环路入口点上。

From Chinese version: http://blog.csdn.net/sayigood/archive/2009/02/15/3891735.aspx