Fast & Slow Pointers (Tortoise and Hare)

Fast & Slow Pointers (Floyd’s Tortoise and Hare Algorithm)

Problem Scenario / Typical Use Case

Imagine you are analyzing a linked list of user actions in a system, trying to detect if a cycle exists—for example, a user repeatedly performing the same sequence of steps due to a bug.

It’s possible to traverse the list using extra memory, but it’s inefficient. The Fast & Slow Pointers pattern provides an elegant way to detect cycles or repeated sequences without extra space, by moving two pointers at different speeds through the data structure.

Basic Idea

The Fast & Slow Pointers pattern involves two references moving at different speeds:

• Slow pointer: moves one step at a time.
• Fast pointer: moves two steps at a time (or more, depending on the problem).

If the structure has a cycle or repeated sequence, the fast pointer will eventually meet the slow pointer again, indicating a cycle.

Typical operations include:

• Detecting cycles in linked lists.
• Finding the start of a cycle.
• Determining the middle of a list efficiently.
• Detecting repeated sequences in arrays or strings.

Advantages

• Space efficiency: No extra memory is required to detect cycles.
• Versatility: Can find mid-points, lengths of cycles, and repeated sequences.
• Elegance: Simplifies complex problems into elegant pointer movement logic.

Limitations / Considerations

• Only applicable to linear structures where movement by “steps” makes sense, such as linked lists or arrays with index-based traversal.
• Requires careful handling of null or edge cases to avoid runtime errors.
• Understanding the movement dynamics is critical—misalignment of speeds or starting positions can lead to incorrect results.

It assumes constant-time access to next elements

Practical Examples / Thought Triggers

1. Cycle Detection in Linked Lists: Classic “Tortoise and Hare” problem—fast pointer eventually meets slow pointer if a cycle exists.
2. Finding the Middle Node: Slow pointer moves one step, fast pointer moves two; when fast reaches the end, slow is at the middle.
3. Repeated Sequence Detection in Arrays: Use pointers moving at different rates to find periodic patterns or "pseudo-cycles" without extra memory.

Thought Triggers:

• Can the same technique detect the start of the cycle or just its presence?
• Would using extra memory (hashset) simplify the problem for sparse or small datasets?
• Can this combine with other traversal patterns to extract additional properties like cycle length?

Implementation Example

Here’s a Python example for detecting a cycle in a linked list:

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 and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            # Pointers meet, meaning a cycle exists
            return True  

    return False  # No cycle

# Example usage
# Creating a cycle: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node with val=2)
node4 = ListNode(4)
node3 = ListNode(3, node4)
node2 = ListNode(2, node3)
node1 = ListNode(1, node2)
node4.next = node2  # cycle here

print(has_cycle(node1))  # Output: True

This illustrates how two pointers moving at different speeds can detect a cycle efficiently without extra memory.

Related Articles

• Two Pointers: Fast & Slow is an extension, moving pointers at different speeds instead of just from two ends.
• Linked List Techniques: Often combined with dummy nodes, in-place reversal, or traversal for more complex manipulations.
• Sliding Window / Prefix Sum: Less direct, but similar reasoning about intervals and distances can apply to array problems.