• Articles by category
• Projects
• Recent Changes

• Submit your applet
• Review applets
• Upload File

• All articles

Selected categories:

• Physics
• Electronics
• Bioinformatics
• Biology
• Barcodes
• Astronomy, geography
• Communication
• Mathematics
• Statistics
• Programming
• Games

• Forum and issue tracker
• Help on editing
• Contact

   New articles (RSS)

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.

[Edit]Algorithm

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.

[Edit]Proof

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:

• If both pointers point to the same node, collision has already been detected in the previous iteration.
• If the fast pointer is directly behind the slow pointer, they collide in the next iteration (slow pointer will move by one and fast pointer will move by two).
• If there is one node gap between the fast pointer and slow pointer, in the next iteration this distance decreases and then fast and slow pointers point to adjacent nodes (the case, described above).
• If there is a bigger gap, it decreases by one node during each iteration until there is only one node remaining in between (the case, described above).

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.