Introduction

The Fast and Slow Pointers Pattern, also known as Floyd's Cycle Detection Algorithm (Tortoise and Hare Algorithm), is one of the most common interview patterns for linked lists.

The technique uses two pointers moving at different speeds to detect cycles, locate the middle node, determine cycle length, and solve several optimization problems in O(n) time using O(1) extra space.

---

When Should You Use Fast and Slow Pointers?

Use this pattern when the problem involves:

• Linked Lists
• Detecting cycles
• Finding the middle node
• Finding the start of a cycle
• Happy Number
• Circular Arrays
• Reordering linked lists

---

Basic Idea

Two pointers traverse the same structure.

graph TD
    Slow_Pointer["Slow Pointer"] --> Moves_1_Step["Moves 1 Step"]
    Moves_1_Step["Moves 1 Step"] --> Fast_Pointer["Fast Pointer"]
    Fast_Pointer["Fast Pointer"] --> Moves_2_Steps["Moves 2 Steps"]

If a cycle exists,

graph TD
    Fast["Fast"] --> Slow["Slow"]
    Slow["Slow"] --> They_Meet["They Meet"]

If there is no cycle,

graph TD
    Fast["Fast"] --> NULL["NULL"]
    NULL["NULL"] --> No_Cycle["No Cycle"]

---

Visualization

Linked List Without Cycle

1 → 2 → 3 → 4 → 5 → NULL

S

F

Fast pointer reaches NULL.

No cycle exists.

---

Linked List With Cycle

1 → 2 → 3 → 4 → 5
          ↑       ↓
          └───────┘

Pointer movement

graph TD
    Slow["Slow"] --> Fast["Fast"]
    Fast["Fast"] --> Meet["Meet"]

---

Why Does It Work?

Imagine two runners on a circular track.

• Slow runner moves one step.
• Fast runner moves two steps.

Eventually, the faster runner catches the slower runner.

The same concept applies to linked lists with cycles.

---

Generic Algorithm

Initialize

slow = head

fast = head

while(fast != null && fast.next != null)

    slow = slow.next

    fast = fast.next.next

    if(slow == fast)

        Cycle Found

Return

---

Java Example (Detect Cycle)

class ListNode {

    int val;
    ListNode next;

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

}

public class DetectCycle {

    public boolean hasCycle(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null &&
               fast.next != null) {

            slow = slow.next;

            fast = fast.next.next;

            if (slow == fast) {
                return true;
            }

        }

        return false;

    }

}

---

Internal Working

Example

1 → 2 → 3 → 4 → 5
      ↑       ↓
      └───────┘

Iteration 1

Slow = 2

Fast = 3

Iteration 2

Slow = 3

Fast = 5

Iteration 3

Slow = 4

Fast = 4

Cycle Found

---

Finding the Middle Node

Same pattern.

Difference:

There is no cycle.

When

Fast == NULL

Slow points to the middle.

Visualization

graph TD
    N_1_2_3_4_5["1 2 3 4 5"] --> S["S"]
    S["S"] --> F["F"]
    F["F"] --> Middle["Middle"]
    Middle["Middle"] --> N_3["3"]

---

Finding Cycle Start

After detecting the meeting point:

1. Move one pointer back to the head.
2. Keep the other at the meeting point.
3. Move both one step at a time.
4. The point where they meet again is the start of the cycle.

---

Visualization

graph TD
    Head["Head"] --> N_["↑       ↓"]
    N_["↑       ↓"] --> N_1["└───────┘"]
    N_1["└───────┘"] --> Meeting_Point["Meeting Point"]
    Meeting_Point["Meeting Point"] --> Move_Together["Move Together"]
    Move_Together["Move Together"] --> Cycle_Start["Cycle Start"]

---

Complexity Analysis

Operation	Complexity
Time	O(n)
Space	O(1)

---

Common Problems Using This Pattern

Problem	Difficulty
Linked List Cycle	Easy
Linked List Cycle II	Medium
Middle of Linked List	Easy
Happy Number	Easy
Circular Array Loop	Medium
Palindrome Linked List	Easy
Reorder List	Medium

---

Production Use Cases

Memory Management

Detect cyclic references in object graphs.

---

Operating Systems

Identify loops in process scheduling structures.

---

Networking

Detect routing loops in packet forwarding paths.

---

Workflow Engines

Detect infinite execution cycles in workflow definitions.

---

Graph Processing

Identify repeated traversal paths in cyclic structures.

---

Database Query Engines

Detect recursive relationship loops during execution.

---

Compiler Design

Detect cyclic dependencies in module references.

---

Common Mistakes

Moving Both Pointers at the Same Speed

If both pointers move one step,

They never meet uniquely

Cycle detection fails.

---

Missing NULL Checks

Always check

fast != null &&
fast.next != null

before moving the fast pointer.

---

Comparing Values Instead of References

Wrong

slow.val == fast.val

Correct

slow == fast

Pointers must reference the same node.

---

Forgetting Empty Lists

Handle

head == null

correctly.

---

Infinite Loops

Ensure both pointers move during each iteration.

---

Interview Tips

Mention these observations:

• The algorithm is also called Floyd's Cycle Detection Algorithm.
• Fast moves two steps; slow moves one.
• Meeting indicates a cycle.
• Fast reaching NULL indicates no cycle.
• The same pattern solves middle-node and cycle-entry problems.

---

Frequently Asked Interview Questions

1. What is the Fast and Slow Pointers pattern?

Answer

It is a technique where two pointers traverse the same data structure at different speeds to detect cycles or locate specific positions efficiently.

---

2. Why is it called Floyd's Cycle Detection Algorithm?

Answer

The algorithm was proposed by Robert W. Floyd and is widely used to detect cycles in linked lists and other iterative structures.

---

3. What is the time complexity?

Answer

O(n) because each pointer traverses the list at most once.

---

4. What is the space complexity?

Answer

O(1) because only two pointers are maintained.

---

5. Why do the pointers meet in a cycle?

Answer

The fast pointer gains one node on the slow pointer during each iteration within the cycle, guaranteeing that they eventually meet.

---

6. How do you find the middle of a linked list?

Answer

Move the slow pointer one step and the fast pointer two steps. When the fast pointer reaches the end, the slow pointer is at the middle.

---

7. How do you find the starting node of a cycle?

Answer

After detecting a meeting point, move one pointer to the head. Move both pointers one step at a time. Their next meeting point is the start of the cycle.

---

8. What is the difference between Two Pointers and Fast & Slow Pointers?

Answer

General Two Pointers may move independently in arrays or strings, while Fast & Slow Pointers specifically move at different speeds, primarily in linked-list-based problems.

---

9. Where is this pattern used in production?

Answer

Memory management, networking, workflow engines, graph traversal, compiler dependency analysis, and recursive processing systems.

---

10. Which interview problems commonly use this pattern?

Answer

Linked List Cycle, Linked List Cycle II, Middle of Linked List, Happy Number, Circular Array Loop, Palindrome Linked List, and Reorder List.

---

Quick Revision

Topic	Summary
Pattern	Fast & Slow Pointers
Also Known As	Floyd's Cycle Detection
Best Complexity	O(n)
Extra Space	O(1)
Best For	Linked Lists & Cycle Detection
Main Idea	Fast = 2 Steps, Slow = 1 Step
Interview Frequency	⭐⭐⭐⭐⭐

---

Key Takeaways

• Fast and Slow Pointers is one of the most important linked-list interview patterns.
• It detects cycles without using additional memory.
• The same technique solves middle-node, cycle-entry, and Happy Number problems.
• It achieves O(n) time with O(1) extra space.
• Mastering this pattern is essential for solving many medium-level coding interview questions efficiently.

---