Cycle Detection Algorithms

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:

1. Initialize two-pointers and start traversing the linked list.

2. Move the slow pointer by one position.

3. Move the fast pointer by two positions.

4. 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:

1. 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.

2. 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.

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

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

5. 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.