This article describes the algorithm to a find loop in the directional linked list, where every node has a pointer (or other reference) to the next node but is not aware where the parent node is. Normally linked lists do not contain any loops and many lists that use algorithms may hang if such loops are present. In some cases loops may form as a result of various malfunctions or even malicious activities (passing the forged cycle that contains loop as parameter).
The described algorithm uses only very small additional space, not dependent on the size of the list. In case if no loops are present it requires somewhat O(n) computing time.
Define two pointers A and B, initially pointing to the beginning of the list. repeat advance A by one (to the next element) advance B by two (to the next element of the next element) until A == B (loop detected) or B reaches the end of the list.
The first pointer is moving two times slower than the second pointer, so if the list has no loops they will never point to the same element. A loop in the list places the faster pointer behind the slower pointer, sooner or later making them to collide.
This algorithm is known for use from the programmer folklore; if you now the serious reference where it is describe please help us by adding it here.
As the time, required to move the pointers over all length of the list is proportional to the number of nodes, the algorithm takes somewhat O(n) time to scan a list that actually has no loops.
It may be some intuitive doubts that the fast pointer may jump over slow pointer without colliding. Anyway, it moves over two nodes during iteration when the slow pointer moves over one! However case by case analysis shows that this will not happen:
Hence the pointers cannot escape collision and there is no need to take additional steps in the algorithm for detection that the nodes are just near to each other.