Today we will discuss three algorithms to detect cycles in a linked list:

Floyd's Tortoise and Hare Algorithm

Brent's Algorithm

Gosper's Algorithm

**1. Floyd's Tortoise and Hare Algorithm**

Floyd’s cycle finding algorithm or Hare-Tortoise algorithm is a pointer algorithm that uses only two pointers, moving through the sequence at different speeds. The algorithm is named after Robert W. Floyd, who was credited with its invention by Donald Knuth.

**Pseudocode:**

Initialize two-pointers and start traversing the linked list.

Move the slow pointer by one position.

Move the fast pointer by two positions.

If both pointers meet at some point then a loop exists and if the fast pointer meets the end position then no loop exists.

Following is the Python3 program to implement the above approach:

```
# Python program to implement
# Floyd's cycle detection
# algorithm to detect cycle
# in a linked list.
class Node:
# Constructor to initialize
# the node object
def __init__(self, data):
self.data = data
self.next = None
# detect if there is a loop in the linked list
def detect_loop(start) -> bool:
slow_pointer = start
fast_pointer = start
while slow_pointer is not None and fast_pointer is not None and fast_pointer.next is not None:
slow_pointer = slow_pointer.next
fast_pointer = fast_pointer.next.next
if slow_pointer == fast_pointer:
return True
return False
# inserting new values
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)
# No loop test
if detect_loop(head):
print("Loop exists in the Linked List")
else:
print("Loop does not exists in the Linked List")
# Expected output: Loop does not exists in the Linked List
# Now adding a loop for demonstration
temp = head
while temp.next is not None:
temp = temp.next
temp.next = head
if detect_loop(head):
print("Loop exists in the Linked List")
else:
print("Loop does not exists in the Linked List")
# Expected output: Loop exists in the Linked List
```

*Time complexity:* O(n), as the loop is traversed once.*Auxiliary Space:* O(1), only two pointers are used therefore constant space complexity.

**2. Brent's Algorithm**

Richard P. Brent described an alternative cycle detection algorithm that, like the tortoise and hare algorithm, requires only two pointers into the sequence. But there is some difference in their approaches. Here we make one pointer stationary till every iteration and teleport it to the other pointer at every power of two. The start of the cycle is determined by the smallest power of two at which they meet. This improves upon the constant factor of Floyd’s algorithm by reducing the number of calls.

**Pseudocode:**

Move the fast pointer (or second_pointer) in powers of 2 until we find a loop. After every power, we reset the slow pointer (or first_pointer) to the previous value of the second pointer. Reset length to 0 after every power.

The condition for loop testing is that first_pointer and second_pointer become the same. And the loop is not present if the second_pointer becomes NULL.

When we come out of the loop, we have the length of the loop.

We reset the first_pointer to the head and the second_pointer to the node at position head + length.

Now we move both pointers one by one to find the beginning of the loop.

```
# Python program to implement
# Brent's cycle detection
# algorithm to detect cycle
# in a linked list.
from typing import Union
class Node:
# Constructor to initialize
# the node object
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to insert a new Node
# at the beginning
def push(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def brent(self) -> Union[Node, bool]:
current_node = self.head
# if head is null then no loop
if not current_node:
return False
first_pointer = current_node
second_pointer = current_node.next
power = 1
length = 1
# This loop runs till we find the loop. If there
# is no loop then second pointer ends at None
while second_pointer and second_pointer != first_pointer:
# condition after which we will update the power
# and length as smallest power of two gives the start of cycle
if length == power:
# updating the power.
power *= 2
# updating the length
length = 0
first_pointer = second_pointer
second_pointer = second_pointer.next
length = length + 1
# if second_pointer is null then no loop
if second_pointer is None:
return False
"""
Otherwise length stores actual length of loop.
If needed, we can also print length of loop:
print("Length of loop is ")
print (length)
"""
# Now set first_pointer to the beginning and
# second_pointer to beginning plus cycle length which is length
first_pointer = second_pointer = self.head
while length > 0:
second_pointer = second_pointer.next
length = length - 1
# Now move both pointers at same speed so that
# they meet at the beginning of loop
while second_pointer != first_pointer:
second_pointer = second_pointer.next
first_pointer = first_pointer.next
return first_pointer
# Driver program for testing
test_list = LinkedList()
test_list.push(50)
test_list.push(20)
test_list.push(15)
test_list.push(4)
test_list.push(10)
# No loop test
res = test_list.brent()
if res:
print("Loop found at ", end=' ')
print(res.data)
else:
print("No loop")
# Now create a loop for demonstration
test_list.head.next.next.next.next.next = test_list.head.next.next
res = test_list.brent()
if res:
print("Loop found at ", end=' ')
print(res.data)
else:
print("No loop")
```

*Time Complexity:* O(m + n) where m is the smallest index of the sequence which is the beginning of a cycle, and n is the cycle’s length.*Auxiliary Space:* O(1)

**Comparison with Floyd’s Algorithm:**

Finds the length of loop in first cycle detection loop itself. No extra work is required for this.

We only move second in every iteration and avoid moving first (which can be costly if moving to next node involves evaluating a function).

**3. Gosper's Algorithm**

R. W. Gosper's algorithm finds the period λ, and the lower and upper bound of the starting point, µ_{l} and µ_{u}, of the first cycle. The difference between the lower and upper bound is of the same order as the period, i.e. µ_{l } + λ ~ µ_{h}.

**Advantages**

The main feature of Gosper's algorithm is that it never backs up to reevaluate the generator function, and is economical in both space and time. It could be roughly described as a concurrent version of Brent's algorithm. While Brent's algorithm gradually increases the gap between the tortoise and hare, Gosper's algorithm uses several tortoises (several previous values are saved), which are roughly exponentially spaced. According to the note in HAKMEM item 132, this algorithm will detect repetition before the third occurrence of any value, i.e. the cycle will be iterated at most twice.