Fast & Slow Pointers

What you'll learn

• The Golden Rule

  Use fast and slow pointers whenever you need to: - Detect a cycle in a linked list or sequence - Find the middle element of a linked list in one pass - Check if a linked list is a palindrome - Detect cycles in any sequence that can be mo…

• Floyd's Cycle Detection

• The Setup

  Two pointers start at the head of a linked list: - Slow pointer moves 1 step per iteration - Fast pointer moves 2 steps per iteration

• Why They Must Meet (If a Cycle Exists)

• What If There's No Cycle?

  If the list is finite with no cycle, the fast pointer reaches null before any meeting occurs. This is how we distinguish "has cycle" from "no cycle."

• Algorithm

  ---

• Finding the Cycle Start

  Once we know a cycle exists (slow and fast met), we can find where the cycle begins.

• The Math

• The Algorithm

  After detection, place one pointer at the head and keep the other at the meeting point. Move both at speed 1. They meet at the cycle start. ---

• Finding the Middle of a Linked List

• The Insight

  When the fast pointer reaches the end of the list, the slow pointer is at the middle — because fast covered twice the distance.

• Algorithm

  For even-length lists, this returns the second of the two middle nodes. To get the first middle node instead, check fast.next and fast.next.next. ---

• Palindrome Linked List

• Strategy

  1. Find the middle using fast/slow pointers 2. Reverse the second half of the list 3. Compare first half with reversed second half

• Algorithm

  ---

• Happy Number

  A happy number is defined by repeatedly replacing a number with the sum of squares of its digits. If this process reaches 1, the number is happy. If it loops endlessly, it is not.

• The Cycle Connection

  The digit-square-sum process either: - Reaches 1 (and stays at 1, since 1 squared = 1) - Enters a cycle that never includes 1 This is exactly a cycle detection problem! The sequence of sums is like a linked list that either terminates at…

• Algorithm

  ---

• Cycle in a Circular Array

• Problem

  Given a circular array of integers (positive = move forward, negative = move backward), determine if there is a cycle. The cycle must: - Have more than one element - All movements in the cycle go the same direction (all positive or all n…

• Approach

  For each starting index, use fast/slow pointers following the direction of movement. Check if a valid cycle forms. ---

• Complexity Summary

  | Problem | Time | Space | |---------|------|-------| | Cycle detection | O(n) | O(1) | | Find cycle start | O(n) | O(1) | | Find middle | O(n) | O(1) | | Palindrome check | O(n) | O(1) | | Happy number | O(log n) | O(1) | | Circular arr…

• Pattern Recognition Checklist

  Ask yourself: 1. Is there a sequence where each element has exactly one "next" element? 2. Could this sequence cycle back on itself? 3. Do I need to find a midpoint without knowing the length? 4. Am I comparing the first half with the se…