A well-known interview question: How to determine if a linked-list has a loop? The answer is to have two pointers scanning the linked-list. If the linked-list doesn’t contain any loop, we should be able to find the end of the linked-list. If the linked-list does contain a loop, then with one pointer advancing one node at a time and the other advancing two nodes at a time, they eventually collide.

But why? Let us represent the linked list as a function $$f(i)$$, which $$i$$ is the ordinal number of the element of the linked list. Assume the linked list has a loop of length $$T$$, then $$f(i+T)=f(i)$$ for some large enough $$i\ge m$$. Therefore, with two pointers, we are checking if $$f(i)=f(2i)$$ for $$i=1,2,\cdots$$. Since $$f(i+T)=f(i)$$, we also have $$f(i+kT)=f(i)$$ for $$i\ge m$$. Hence, for $$k'T\ge m$$, we have $$f(k'T+k'T)=f(k'T)$$ or $$f(2k'T)=f(k'T)$$. Thus whenever there is a loop, such algorithm can find it. Moreover, once $$f(i)=f(2i)$$ is found, $$T$$ is a factor of $$i$$ and $$m\le i$$.