How to determine whether there are circles in a singly linked list?
Answer：let to point p1 ,and p1 , p1 travels the list with one step length ,and p2 with two step length ,
After t step , if p2 come to same pos with p1 , we get there is an circle , otherwise no circle exist in list.
Now let’s prove it .
Both p1 and p2 travel the list ,but with diff step length, where p1 is a one step traveler and P2 is a two step traveler.
Exist and only exist two conditions:
1. Condition one: P2 come to the end. we get there is on circle , it’s trival.
2. Condition two：P2 come to same pos with p1, we got more than one circle exist.
Let there is a circle as the picture below:
Suppose: When p1 come to the first pos (N1) of the circle, P2 is at pos Nk(where K should be one of 1…N).
After t step :
P1 come to N(t1) where t1=t%N
P2 come to N(t2) whereK2=(k+2t)%N
Principal : t , t is a natural number , let t+n*m=k+2t , so t1=t2 and P1 come to same pos with P2. where m is natural number
Proof:
Let t=m*n-k we get it, m is a positive natural number.
口.
