Two Pointers: Fast & Slow Resource

Two Pointers: Fast & Slow Resource - aloalgo

The fast and slow pointer technique (also called Floyd's algorithm) uses two pointers moving at different speeds. The slow pointer moves one step at a time, while the fast pointer moves two steps. This pattern is essential for linked list problems.

This simple pattern solves two common problems:

Finding the middle: When fast reaches the end, slow is at the middle
Detecting cycles: If there's a cycle, fast and slow will eventually meet

When the fast pointer reaches the end of the list, the slow pointer will be at the middle. This works because fast moves twice as fast as slow.

Time: O(n) - single pass through the listSpace: O(1) - only two pointers

Idea: If there's a cycle, the fast pointer will eventually catch up to the slow pointer. If fast reaches the end (null), there's no cycle.

Time: O(n)
Space: O(1)

Once we detect a cycle, we can find where it starts. After slow and fast meet, reset one pointer to head and move both at the same speed. They'll meet at the cycle's start.

The math: Let's say the distance from head to cycle start is a, and the meeting point is b nodes into the cycle. When they meet, slow has traveled a + b, and fast has traveled 2(a + b). The extra distance fast traveled is exactly the cycle length. This means moving a more steps from the meeting point brings us back to the cycle start.

Use fast/slow to find middle, reverse second half, compare.

Floyd's algorithm can also solve the "find duplicate in array" problem by treating the array as a linked list where nums[i] points to the next node.

A number is "happy" if repeatedly summing the squares of its digits eventually reaches 1. If it enters a cycle, it's not happy. Use Floyd's algorithm to detect the cycle.

Check fast.next: Always check both fast and fast.next before advancing to avoid null pointer errors.
Know both applications: The same pattern solves cycle detection and finding the middle.
Space efficiency: This technique uses O(1) space compared to O(n) for using a hash set.
Think abstractly: Any sequence where each element points to another (like array indices) can be treated as a linked list for cycle detection.

Was this helpful?

Study plan All problems

Resources Cheat Sheet DSA Glossary

Two Pointers: Fast & Slow

The Pattern

Find Middle of Linked List

Detect Cycle in Linked List

Find Where Cycle Begins

Palindrome Linked List

Find the Duplicate Number

Happy Number

Common Interview Tips

Practice Problems

Company

Practice

Learn