Loop & Its Entrance in Singly Linked List

Problem:
Given a singly linked list, check whether there is a loop in it. If yes, find the entrance to the loop.

Thinking:
Use 2 pointers, one fast and one slow. If at some time, these 2 pointers meet, then there is a loop; if fast pointer arrives at the end of the list, there is no loop.

Suppose we have above list structure. Assume loop length is \(r(r\in N)\), and the length before the loop (from \(A\) to \(B\)) is \(l\). Always, one can represent \(l\) as \(l=k\cdot r+p\), where \(k=0,1,2,...\) and \(p=0,1,2,...,r-1\).

Then, suppose the moving speed of "fast" is \(a\) times of "slow", where \(a>1\) and \(a\in N\). If "slow" moves one step a time, "fast" will move \(a\) steps a time.

If there is a loop, where will the 2 pointers meet? Suppose they will meet after "fast" finishes \(n\) loops and "slow" finishes \(m\) loops. And suppose also, at this moment, they are at point C, which is of \(q\) steps after the loop entrance \(B\). Here, \(n\ge1, m\ge0, m,n\in N, q=0,1,...,r\). Hence, the following equation holds: \[k\cdot r+p+n\cdot r+q=a(k\cdot r+p+m\cdot r+q)\] We need find values for \(m,n\) and \(q\) so that above equation holds. The equation can be rewritten as \[n\cdot r-a\cdot m\cdot r-k(a-1)r=(a-1)(p+q)\] We can always find a \(q\) such that \(p+q=r\), then \[n-am-k(a-1)=a-1\] \[n=am+(k+1)(a-1)\] For the first time they meet, \(m=0\) and then \[n=(k+1)(a-1)\] To be most efficient, \(a=2\) and \(n=k+1\).

Conclusion:
From above statement, we know that "fast" and "slow" will definitely meet during the first loop round for "slow". Also, at the moment they meet, they are at \(q=r-p\) steps after \(B\), which is equivalent to \(p\) steps before \(B\). Note that the head length \(l=k\cdot r+p\), which means that if two pointers start at \(A\) and \(C\) at the same time and both move one step a time, they will meet at the loop entrance \(B\) for the first time.

Below, I just show the code to find the loop entrance. Actually, the loop check is just part of and can be told from the return value of this program.