Fast & Slow Pointers (Cycle Detection)

OVERVIEW

The Fast & Slow Pointers pattern uses two pointers moving through the data
structure at different speeds.

Typically:

• slow moves one step at a time
• fast moves two steps at a time

This pattern is most famous for detecting cycles in linked lists, but it is also
used for finding the middle of a list, cycle length, and cycle start.

WHY IT WORKS

If a cycle exists:

• The fast pointer will eventually lap the slow pointer
• Both pointers will meet inside the cycle

If no cycle exists:

• The fast pointer will reach the end (null)

TIME & SPACE

Time Complexity : O(N)
Space Complexity : O(1)

EXAMPLE 1: Detect Cycle in a Linked List (Floyd’s Algorithm)

Problem:
Determine whether a linked list has a cycle.

Logic:

• Move slow by 1 step
• Move fast by 2 steps
• If they ever meet, a cycle exists

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

def has_cycle(head):
slow = head
fast = head

while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
        return True

return False

EXAMPLE 2: Find the Starting Point of the Cycle

Problem:
If a cycle exists, find the node where the cycle begins.

Key Insight:

• When slow and fast meet, move one pointer to head
• Move both one step at a time
• The point where they meet again is the cycle start

def detect_cycle_start(head):
slow = head
fast = head

while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
        break
else:
    return None

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

return slow

EXAMPLE 3: Find Length of the Cycle

Problem:
Given a linked list with a cycle, determine the length of the cycle.

Logic:

• After slow and fast meet, keep one pointer fixed
• Move the other pointer until it meets again

def cycle_length(head):
slow = head
fast = head

while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
        length = 1
        current = slow.next

        while current != slow:
            length += 1
            current = current.next

        return length

return 0

EXAMPLE 4: Find Middle of Linked List

Problem:
Return the middle node of a linked list.

Logic:

• Slow moves 1 step
• Fast moves 2 steps
• When fast reaches end, slow is at middle

def middle_node(head):
slow = head
fast = head

while fast is not None and fast.next is not None:

    slow = slow.next

    fast = fast.next.next

return slow

IDENTIFICATION CHECKLIST

Ask these questions:

• Do two pointers move at different speeds?
• Is the structure sequential (linked list / array)?
• Is there a cycle or repetition possibility?
• Do I need middle or loop information?

If yes, Fast & Slow Pointers is the right pattern.

SUMMARY

• Two pointers, different speeds
• Guaranteed meeting point if cycle exists
• Elegant, math-backed solution
• Core interview pattern worth mastering