What is Floyd's Cycle Detection Algorithm?

Floyd's Cycle Detection Algorithm, also known as the 'Tortoise and Hare' algorithm, is a pointer algorithm that uses two pointers which move at different speeds to detect a cycle in a sequence of values, such as a linked list.

How does the Tortoise and Hare algorithm work?

It uses two pointers, a 'slow' pointer (the tortoise) that moves one step at a time, and a 'fast' pointer (the hare) that moves two steps at a time. If there is a cycle, the fast pointer will eventually lap the slow pointer.

Linked Lists

Floyd's Cycle Detection

The 'Tortoise and Hare' algorithm provides an elegant O(n) time and O(1) space solution for detecting cycles in linked lists. A must-know for interviews.

Linked List Cycle Detection

This implementation uses a slow and a fast pointer to determine if a linked list has a cycle. If the pointers meet, a cycle exists.

                            function hasCycle(head) {
                            let slow = head;
                            let fast = head;
                            
                            while (fast && fast.next) {
                            slow = slow.next;
                            fast = fast.next.next;
                            if (slow === fast) {
                            return true;
                            }
                            }
                            
                            return false;
                            }
                        

AI Coach Hint: The condition `fast && fast.next` is crucial. It prevents errors when the list is empty, has one node, or when the fast pointer reaches the end of a non-cyclic list. This check ensures `fast.next.next` is safe to access.