Fast & Slow Pointers (Floyd's)

1. Introduction

What is the Fast & Slow Pointer Pattern?

The Fast & Slow Pointer Pattern (also known as Floyd's Cycle-Finding Algorithm or the Runner Technique) uses two pointer references that traverse a linked list at different speeds:

The Slow pointer advances 1 node per iteration.

The Fast pointer advances 2 nodes per iteration.

Why is it Important?

This technique allows you to detect cycles (loops) and identify structural milestones (like finding the exact middle node of a list) in O(N) time and O(1) space. Without it, cycle detection would require storing seen node references in a HashSet, taking O(N) auxiliary memory.

Where is it Used?

Network Routing: Detecting looping routes in packet logs.

Memory allocators: Scanning for corrupted circular linked list buffers.

---

2. Mental Model: Tortoise and Hare on a Circular Track

Imagine a tortoise (slow) and a hare (fast) racing:

If they are running on a straight path, the hare will reach the end line and disappear, while the tortoise is still halfway.

If they are running on a circular loop, the hare will loop around endlessly. Eventually, because it runs twice as fast, the hare will "lap" the tortoise, and they will meet at the same location!

---

3. Core Algorithms & Implementations

1. Middle of the Linked List (LeetCode 876)

Initialize slow and fast pointers at head.

Advance fast by 2 steps (fast = fast.next.next) and slow by 1 step (slow = slow.next) while fast != null and fast.next != null.

When fast reaches the end, slow will point to the exact middle node of the list.

2. Linked List Cycle Detection (LeetCode 141)

If slow and fast pointers meet (slow == fast), a cycle is present.

If fast or fast.next becomes null, no cycle exists.

3. Finding the Start of the Cycle (LeetCode 142)

Run the cycle detection. Once slow and fast meet, keep fast at the meeting point and place slow back at head.

Advance both pointers at the same speed (1 step per iteration). The node where they meet next is the starting node of the cycle.

---

4. Mathematical Proof: Floyd's Cycle Detection Start

Let's understand why resetting one pointer to head and advancing both 1 step at a time locates the cycle starting node:

Distance traveled by slow = A + B.

Distance traveled by fast = A + B + N × L (where N is the number of cycles run).

Since fast runs twice as fast:

We know L = B + C, so:

This mathematical identity means that the distance A from the head to the cycle start is equivalent to the distance C from the meeting point back to the cycle start (plus any full cycles). Thus, moving both pointers 1 step at a time guarantees they will meet at the cycle start!

---

5. Real-World Applications

Dynamic Heap Garbage Collectors: Detecting reference memory leak cycles during object collection cycles.

Network Topologies Verification: Resolving spanning tree configurations and avoiding circular network packet routes.

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers test pointer-chasing mechanics:

"Given a linked list, check if it is a palindrome." -> Find the middle of the list using fast/slow pointer, reverse the second half, then compare both halves.

"Find the length of the cycle if present." -> Once slow and fast meet, keep fast still and advance slow 1 step at a time, incrementing a count, until they meet again.

Common Mistakes

> 2. Wrong Midpoint for Even Lists: If a list has 6 nodes (1 -> 2 -> 3 -> 4 -> 5 -> 6), fast/slow ends with slow at 4 (the second middle). If you want the first middle (3), adjust loop bounds.

---

7. Summary

Tortoise and Hare: Slow moves 1 step; fast moves 2 steps.

Midpoint: When fast reaches null, slow is at the middle.

Cycles: If slow and fast meet, a cycle exists.

Start Node: Reset one pointer to head and move both at 1 step to find cycle origin.

---

8. Quiz

Question 1: Why does the fast pointer skip 2 nodes instead of 3?

Answer: If the fast pointer skipped 3 nodes, it might skip over the slow pointer entirely inside the cycle without landing on the exact same node, which would cause an infinite loop in our detection code. Advancing by 2 guarantees they will eventually meet.

Question 2: What is the space complexity of Floyd's Cycle-Finding Algorithm?

Answer: O(1) auxiliary space. We only allocate two pointer variables (slow and fast), regardless of list size.

Question 3: In finding the midpoint of a list with 5 nodes (1 -> 2 -> 3 -> 4 -> 5), where does the slow pointer stop?

Answer: Node 3 (the exact middle).

Question 4: True or False: If a cycle start node is the head node itself, slow and fast will meet at the head node.

Answer: True. The meeting point inside the cycle will result in the reset phase meeting immediately at the head.

Question 5: How does this pattern help solve the 'Happy Number' problem?

Answer: A number is happy if the sum of squares of its digits eventually hits 1. If it doesn't, it loops in a cycle. We can treat numbers as nodes where the next pointer is the digit square sum, and use Floyd's algorithm to detect the cycle.