Floyd’s Cycle Detection Algorithm

Floyd’s Cycle Detection Algorithm is an algorithm used to detect the presence of a cycle in a linked list and, if a cycle exists, to find the starting point of that cycle.

This algorithm uses two pointers: one moves one step at a time (slow), and the other moves two steps at a time (fast). Because of this structure, it is also known as the Fast and Slow Pointer Algorithm or the Tortoise and Hare Algorithm.

[Algorithm Implementation]

# Definition for singly-linked list node.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
 # 1. detect the presence of a cycle
    def hasCycle(self, head: ListNode) -> bool:
        tortoise = head # slow pointer
        hare = head # fast pointer

        while hare and hare.next:
            tortoise = tortoise.next # moves one step
            hare = hare.next.next # moves two step

            if tortoise == hare:
                return True
        return False

 # 2. find the starting point of that cycle
    def detectCycle(self, head: ListNode) -> ListNode:
        tortoise = head
        hare = head

        while hare and hare.next:
            tortoise = tortoise.next
            hare = hare.next.next

            if tortoise == hare: # If a cycle exists
                tortoise = head # move one pointer to the head of the list.
                while tortoise != hare:
                    tortoise = tortoise.next
                    hare = hare.next
                return tortoise
        
        return None

hasCycle method
Traverse the linked list using two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. If the two pointers meet during traversal, it indicates that a cycle exists.

detectCycle method
Check for the meeting of the two pointers in the same way as in hasCycle.
If the pointers meet, move the slow pointer to the head of the linked list, then advance both slow and fast pointers one step at a time. The node where the two pointers meet again is the starting point of the cycle.

[How the Algorithm Works]

[1] Why do the two pointers meet if a cycle exists?
Intuitively, if there is no cycle, the fast pointer will reach the end of the linked list (null) before the slow pointer, so the two pointers will never meet.
On the other hand, if a cycle exists, the fast pointer will eventually catch up to the slow pointer within the cycle. Because the fast pointer moves twice as fast as the slow pointer, it gains one step on the slow pointer in each iteration, so they must meet at some node inside the cycle.

Get Woolaf's Techscope’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

[2] Why does moving one pointer to the head and advancing both one step at a time make them meet at the start of the cycle?

P0 : the distance from the head of the linked list to the start of the cycle.
P1 : the distance from the start of the cycle to the point where the two pointers meet.
C : the length of the cycle.

Let’s start with the simplest case. Imagine the slow pointer (the tortoise) has moved P0 + P1 steps, while the fast pointer (the hare) has completed one full cycle plus those same P0 + P1 steps to catch up with the tortoise.
Since the hare moves twice as fast, its total distance traveled is twice that of the tortoise: 2(P0 + P1) = P0 + P1 + C which simplifies to P0 = C — P1. This means that if you move from the meeting point ahead by P0 steps, you reach the start of the cycle.

Now, let’s look at it more rigorously. Suppose the slow pointer has traveled a total distance of P0 + P1. Since the fast pointer moves twice as fast, it has traveled 2(P0 + P1) steps. Because each pointer may have looped around the cycle multiple times, the difference in distance traveled by the two pointers must be a multiple of the cycle length C.

2(P0 + P1) - (P0 + P1) = P0 + P1 = kC
P0 = kC - P1

If we now move the slow pointer back to the head of the list and keep the fast pointer at the meeting point, and advance both pointers one step at a time, the slow pointer will move P0 steps while the fast pointer will move C - P1 steps inside the cycle.

P0 = kC - P1 ≡ C - P1 (mod C)

they will meet exactly at the start of the cycle.

The modulo operation is used here because we are interested in their positions within the cycle, not the total distance traveled, and multiples of the cycle length C correspond to the same position within the cycle.