Floyd’s tortoise and Hare cycle finding algorithm is used to find cycles/loops in a linked list data structure. Before learning how this algorithm works, let’s first look at what a linked list data structure is and what cycles are.
Linked List Data Structure
Linked list is a data structure which is made of several nodes and each node has the address of the next node. For example A->B->C is a linked list with 3 nodes A, B & C where node A points to node B and node B points to node C. Also each node can store a certain value.
Cycle or Loop in a Linked List
Now let’s consider a scenario where node A points to node B, node B points to node C and node C points back to node A. Something like this: A->B->C->A:
Now when we try to visit all the nodes, we first visit node A, then node B, then node C. Node C is connected back to node A. So next we visit node A and the sequence repeats again and again. This is termed as a linked list with a cycle or loop. If the algorithm used to visit all the nodes in a linked list is not intelligent, it might visit every node in the loop infinitely untill someone interrupts it.
Cycle finding algorithms can be used to find out if there are loops like the ones we discussed. Floyd’s tortoise and hare algorithm is one such algorithm that can detect cycle or loop in a linked list in O(N) time (Time proportional to the length of linked list).
Idea Behind the Algorithm
The idea behind Floyd’s Tortoise and Hare cycle finding algorithm is to have 2 pointers (markers): slow pointer (tortoise) and fast pointer (hare). The slow pointer moves one node at a time, whereas the fast pointer moves two nodes at a time. Effectively the relative movement between the two pointers is one node per pointer move. i.e., if both fast pointer and slow pointer is moved n times, there will be n-1 nodes between them. Below is the animation on how slow and fast pointers are moved:
If the fast pointer reaches a node where the next node is null (last node) or if next node is the last node, we can safely conclude that we reached end of the list and there are no cycles in the list. Also the slow pointer never catches up with the fast pointer.
But if the given linked list contains a loop, both slow and fast pointers enter the loop and continue moving inside the loop. Once the slow and fast pointers are inside the loop, the fast pointer gets one node closer to the slow pointer with every move. And so both the pointers will meet at a certain node in the loop after certain moves. You can slideshow below for better understanding:
So while advancing slow pointer and fast pointer, if we observe that both slow and fast pointers somehow reached the same node, it means that there is a cycle within the linked list.
Implementing Floyd’s Cycle Finding Algorithm
# Python code to implement
# Floyd's Tortoise Hare Algorithm
# Class to represent a linked list node
class Node:
def __init__(self, d):
self.data = d
self.next = None
# Function implementing
# cycle finding algorithm
def detectLoop(head):
slowPointer = head
fastPointer = head
while (slowPointer != None
and fastPointer != None
and fastPointer.next != None):
slowPointer = slowPointer.next
fastPointer = fastPointer.next.next
if (slowPointer == fastPointer):
return 1
return 0
# Let's create a linked list with a loop
# And test the algorithm
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
head.next.next.next = Node(40)
head.next.next.next.next = Node(50)
head.next.next.next.next.next = head # Loop!
# Let's test the algorithm now
# with the looped linkedlist
if (detectLoop(head)):
print("Loop exists in the Linked List")
else:
print("Loop does not exists in the Linked List")
Characteristics of Floyd’s Cycle Finding Algorithm
Time Complexity
The number of nodes visited by Floyd’s cycle finding algorithm lies anywhere between N/2 and N nodes before finding out if there is a cycle in the linked list. So the time complexity is O(N).
Space Complexity
Throught all the steps in the algorithm, we store only 2 nodes that correspond to the nodes pointed by slow pointer and the fast pointer. No other additional space is used, so this algorithm has O(1) space complexity.