1. Introduction

The Fast and Slow Pointers pattern (also known as the Tortoise and Hare algorithm) is a powerful technique used for solving problems that involve sequential traversal, particularly in linked lists, arrays, or circular data structures.

The main idea is simple but elegant:
You use two pointers that move through the sequence at different speeds — usually one moves one step at a time (slow pointer) and the other moves two steps at a time (fast pointer).

By comparing the movement and positions of these two pointers, you can detect patterns such as cycles, middle elements, or relative distances between nodes.

2. Why Use Fast and Slow Pointers?

You should consider using this pattern when:

1. Cycle Detection
   You suspect that a linked list or sequence might form a loop or cycle.
   Example: Detecting whether a linked list has a cycle or not.
2. Finding the Middle of a Linked List
   You need to identify the midpoint of a sequence without first counting all elements.
   Example: In problems like “Reorder Linked List” or “Palindrome Linked List”.
3. Detecting Intersection Points
   You want to find the starting node of a loop or intersection point in linked lists.
4. Optimized Searching in Circular or Infinite Sequences
   You are looking for repeating patterns, collisions, or convergence of states.
5. Linked List Reversal Problems
   It’s often used in combination with other techniques (like in palindrome verification).
6. Problems involving two dependent speeds or rates
   Any problem where one object moves faster than another and you want to detect their meeting or relative position.

In short:

If a problem involves two entities moving through a structure at different speeds, or if it involves detecting cycles, midpoints, or collisions, the Fast and Slow Pointer pattern is an ideal fit.

3. How It Works – The Core Concept

Let’s assume we have two pointers:

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

They both start at the head of a linked list or the beginning of an array.

Step-by-Step Working

1. Move both pointers forward:
   • slow = slow.next
   • fast = fast.next.next
2. Continue this process until:
   • The fast pointer reaches the end (in case of no cycle).
   • OR the two pointers meet (in case of a cycle).
3. The meeting point tells you about the structure:
   • If they meet → there is a cycle.
   • If the fast pointer reaches null → there is no cycle.

4. Example 1: Detecting a Cycle in a Linked List

Problem Statement

Given the head of a linked list, determine whether it contains a cycle.

Intuition

If there is a loop, the fast pointer (which moves faster) will eventually lap the slow pointer and meet it inside the cycle.

Java Code Example

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class LinkedListCycle {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;          // move one step
            fast = fast.next.next;     // move two steps

            if (slow == fast) {        // cycle detected
                return true;
            }
        }

        return false; // fast reached null → no cycle
    }
}

Time and Space Complexity

• Time Complexity: O(n) — both pointers traverse at most the length of the list.
• Space Complexity: O(1) — no extra space used.

5. Example 2: Finding the Start of the Cycle

Once you detect a cycle, you can find the starting node of that cycle.

Key Idea

After detection, reset one pointer to the head, and move both pointers one step at a time until they meet again — that node will be the start of the loop.

Java Code

public ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    // First, detect the cycle
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) {
            // Reset slow to head
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow; // start of the cycle
        }
    }

    return null; // no cycle
}

Explanation

• When the slow and fast pointers meet inside the loop,
  the distance from head to loop start equals the distance from meeting point to loop start.
  This elegant property allows the algorithm to work without counting nodes.

6. Example 3: Finding the Middle of a Linked List

This is another very common use case.

Problem

Given a linked list, find its middle node.

Approach

Move the slow pointer one step and fast pointer two steps at a time.
When fast reaches the end, slow will be at the middle.

Java Code

public ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow; // middle node
}

Why It Works

The fast pointer travels twice as fast as the slow one.
So, when fast finishes, slow will have reached halfway.

7. Example 4: Detecting Happy Numbers

The Happy Number problem (LeetCode 202) is another example where the fast and slow pointer logic can be applied even though it’s not a linked list.

Problem Statement

A number is “happy” if repeatedly summing the squares of its digits eventually leads to 1.
If it falls into a loop, it’s not happy.

Code

public class HappyNumber {
    private int nextNumber(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        int slow = n;
        int fast = nextNumber(n);

        while (fast != 1 && slow != fast) {
            slow = nextNumber(slow);
            fast = nextNumber(nextNumber(fast));
        }

        return fast == 1;
    }
}

Intuition

Even though this is not a data structure traversal problem,
the sequence of sums behaves like a linked structure —
if a loop exists, slow and fast will meet inside it.

8. When to Use Fast and Slow Pointers

Use this pattern when:

• The problem involves detecting loops or repetitions.
• You need to find midpoints efficiently in one traversal.
• You’re trying to identify meeting points or convergence of two processes moving at different speeds.
• The sequence of states (numbers, nodes, or array elements) can be traversed deterministically (each step depends on the previous one).

Common Scenarios

1. Linked list problems (cycle detection, middle node, palindrome check)
2. Numerical transformation loops (like Happy Numbers)
3. Array cycle problems (e.g., circular arrays)
4. Two moving entities approaching each other at different speeds

9. Advantages

• No extra memory required – constant space.
• Elegant detection of cycles without using hash sets.
• Single traversal suffices in most cases (O(n) time).
• Extremely efficient for real-time linked list processing.

10. Summary

Concept	Description	Example Problem
Cycle Detection	Find if a loop exists	Linked List Cycle
Find Start of Loop	Locate where cycle begins	Linked List Cycle II
Find Middle	Identify midpoint	Middle of Linked List
Repetition Detection	Check if a state repeats	Happy Number
Collision Detection	Detect convergence of two rates	Race simulation problems

11. Key Takeaways

• The Fast and Slow Pointer technique is one of the most elegant tools for linear data structure problems.
• It avoids extra space and provides O(1) space complexity solutions.
• The key is to identify whether your problem involves two entities moving at different rates, or detecting a cycle or meeting point.
• The principle can be extended beyond linked lists — even to numbers, arrays, and algorithmic processes.