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 , which is the ordinal number of the element of the linked list. Assume the linked list has a loop of length , then for some large enough . Therefore, with two pointers, we are checking if for . Since , we also have for . Hence, for , we have or . Thus whenever there is a loop, such algorithm can find it. Moreover, once is found, is a factor of and .