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$.