Tortoise and Hare Algorithm

#algorithms #beginners #learning #python

We all would have heard about the tortoise and hare story right? Well, there's an algorithm inspired by this story.

What is this Algo?

Floyd's Cycle Detection Algorithm, often referred to as the "tortoise and hare" algorithm, is used to detect the presence of a cycle in a linked list. This algorithm is named after American computer scientist Robert W. Floyd, who described it in 1967. It's a simple yet efficient technique that works by using two pointers to traverse the linked list at different speeds.

Yes, it works like the story. There will be two pointers running simultaneously within the same linked list. If the linked list has a cycle (i.e if the tail is connected to another node) the two pointers will meet together at some point. If not, the pointers will never meet.

First of all, what do I mean by a cycle in a linked list? Refer the below images: image 1 is a linked list without cycle (i.e tail node is not connected to any other node) and image 2 is a linked list with cycle because the tail node (-4) is connected to another node (2) in the list. Floyd's algo is efficient in detecting cycles in the linked lists.

Implementation with python

Below is the implementation of Floyd's algo with python. The detect_cycle method takes in head (LinkNode object) and traverses through the list and checks if the Linked List has a cycle.

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

def detectCycle(head):
    # Initialize two pointers, slow and fast, both initially at the head of the linked list.
    slow = head
    fast = head

    # Step 1: Detect the cycle (Floyd's algorithm)
    while fast and fast.next:
        # Move the slow pointer one step at a time.
        slow = slow.next
        # Move the fast pointer two steps at a time.
        fast = fast.next.next

        # If the slow and fast pointers meet, it indicates the presence of a cycle.
        if slow == fast:
            return True  # Cycle detected

    # If the fast pointer reaches the end of the list (or becomes None), there is no cycle.
    return False  # No cycle found