Detect Loop (Floyd's Cycle Detection) 🎯

Welcome to this comprehensive guide on Floyd's Cycle Detection algorithm, a powerful tool for detecting cycles in a linked list! This tutorial is designed for both beginners and intermediates, covering the concept from scratch and delving into advanced examples. Let's embark on this exciting journey together!

Understanding the Problem 📝

A linked list is a data structure consisting of nodes connected by links. Sometimes, these lists may contain cycles – a situation where a node points back to a previously visited node. Detecting cycles in a linked list is a fundamental problem in computer science.

Floyd's Cycle Detection Algorithm 💡

Floyd's Cycle Detection algorithm is a simple, linear-time, and space-efficient method for detecting cycles in a linked list. It works by using two pointers – a fast pointer and a slow pointer – that traverse the list at different speeds.

The Fast and Slow Pointers 📝

Fast Pointer (fast): This pointer moves k steps ahead with each step, where k > 1. In the original algorithm, k = 2.
Slow Pointer (slow): This pointer moves one step ahead with each step.

How it works 💡

If there is no cycle, the fast and slow pointers will never meet.
If there is a cycle, the fast pointer will eventually catch up to the slow pointer.
Once the fast and slow pointers meet, they will keep traversing the cycle together.
To find the beginning of the cycle, move the slow pointer to the head of the list, and both pointers k - 1 steps ahead. Now, both pointers will traverse the cycle simultaneously, and they will meet at the beginning of the cycle.

Implementation 💡

Here's a simple implementation of Floyd's Cycle Detection algorithm in Python:

python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def detect_cycle(head):
    fast = head.next.next if head.next else None
    slow = head

    while fast and fast != slow:
        fast = fast.next.next if fast.next else None
        slow = slow.next

        if fast == slow:
            return True

    if fast is None:
        return False

    slow2 = head
    while slow != fast:
        slow = slow.next
        slow2 = slow2.next

    return slow

Let's break down the code:

We first define a Node class to represent the linked list nodes.
The detect_cycle function takes the head of the linked list as input.
We initialize the fast and slow pointers. If the linked list does not have a cycle, the fast pointer will be None.
The while loop checks for a cycle by comparing the positions of the fast and slow pointers.
If there is a cycle, the fast and slow pointers will meet, and the function returns True.
If there is no cycle, the function returns False.
If a cycle is detected, the function finds the beginning of the cycle by moving the slow pointer and a new pointer (slow2) simultaneously.

Practice Time 🎯

Wrapping Up 🎯

Congratulations! You've successfully learned Floyd's Cycle Detection algorithm, a powerful tool for detecting cycles in a linked list. Remember, practice makes perfect! Experiment with different scenarios and linked lists to deepen your understanding of this fascinating algorithm. Keep coding and learning! 💡💡💡