In this post, we will be discussing Floyd’s cycle detection algorithm. So, let’s dive into it!
Floyd’s cycle detection algorithm
Floyd’s cycle-finding algorithm is a pointer algorithm that uses only two pointers, moving through the sequence at different speeds. It states the usage of Linked List in this algorithm and its output.
It is also called the “tortoise and the hare algorithm”, alluding to Aesop’s fable of The Tortoise and the Hare.
The algorithm is named after Robert W. Floyd, who was credited with its invention by Donald Knuth. However, the algorithm does not appear in Floyd’s published work, and this may be a misattribution: Floyd describes algorithms for listing all simple cycles in a directed graph in a 1967 paper, but this paper does not describe the cycle-finding problem in functional graphs that is the subject of this article. In fact, Knuth’s statement (in 1969), attributing it to Floyd, without citation, is the first known appearance in print, and it thus may be a folk theorem, not attributable to a single individual.
The purpose is to determine whether the linked list has a cycle or not. First, you keep two pointers of the head node. At each iteration, you move one of the pointers by two steps and the other one by one step. So you have two pointers tortoise and the hare. Eventually one of the two cases will happen:
- Hare will reach the tail of the linked list(null), which means that there is no cycle in it.
- Hare will meet tortoise, which means that there is a cycle.
Time complexity is O(N) where N is the number of nodes in the linked list, space complexity is O(1) as you use only two pointers.
To sum it up-
Floyd’s cycle detection algorithm is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. The idea is to move the fast pointer twice as quickly as the slow pointer, and the distance between them increases by one at each step. If we both meet at some point, we have found a cycle in the list; otherwise, no cycle is present if the end of the list is reached. It is also called the “tortoise and the hare algorithm”.
The algorithm can be implemented in C++, Java, and Python.
Code in python
# A Linked List Node class Node: def __init__(self, data=None, next=None): self.data = data self.next = next # Function to detect a cycle in a linked list using # Floyd’s cycle detection algorithm def detectCycle(head): # take two references – `slow` and `fast` slow = fast = head while fast and fast.next: # move slow by one slow = slow.next # move fast by two fast = fast.next.next # if they meet any node, the linked list contains a cycle if slow == fast: return True # we reach here if slow and fast do not meet return False if __name__ == '__main__': head = None for i in reversed(range(5)): head = Node(i + 1, head) # insert cycle head.next.next.next.next.next = head.next.next if detectCycle(head): print('Cycle Found') else: print('No Cycle Found')
Cycle detection has been used in many applications.
- Determining the cycle length of a pseudorandom number generator is one measure of its strength. This is the application cited by Knuth in describing Floyd’s method. Brent describes the results of testing a linear congruential generator in this fashion; its period turned out to be significantly smaller than advertised. For more complex generators, the sequence of values in which the cycle is to be found may not represent the output of the generator, but rather its internal state.
- Several number-theoretic algorithms are based on cycle detection, including Pollard’s rho algorithm for integer factorization and his related kangaroo algorithm for the discrete logarithm problem.
- In cryptographic applications, the ability to find two distinct values x(μ−-1) and x(λ+μ−-1) mapped by some cryptographic function ƒ to the same value xμ may indicate a weakness in ƒ. For instance, Quisquater and Delescaille apply cycle detection algorithms in the search for a message and a pair of Data Encryption Standard keys that map that message to the same encrypted value; Kaliski, Rivest, and Sherman also use cycle detection algorithms to attack DES. The technique may also be used to find a collision in a cryptographic hash function.
- Cycle detection may be helpful as a way of discovering infinite loops in certain types of computer programs.
- Periodic configurations in cellular automaton simulations may be found by applying cycle detection algorithms to the sequence of automaton states.
- Shape analysis of linked list data structures is a technique for verifying the correctness of an algorithm using those structures. If a node in the list incorrectly points to an earlier node in the same list, the structure will form a cycle that can be detected by these algorithms. In Common Lisp, the S-expression printer, under control of the print-circle variable, detects circular list structure and prints it compactly.
In this post, we discussed Floyd’s cycle detection algorithm and code it in python.