Fast & Slow Pointers Pattern (Tortoise and Hare)

The Fast & Slow Pointers technique, also known as the "Tortoise and Hare" algorithm, uses two pointers that move through a data structure at different speeds. This pattern is particularly useful for detecting cycles and finding middle elements.

When to Use This Pattern

Detecting cycles in linked lists
Finding the middle element of a linked list
Finding the k-th element from the end
Detecting cycles in arrays (using indices as pointers)
Problems involving "Happy Number" or similar cycle detection

Key Concepts

The pattern uses two pointers:

Slow pointer: Moves one step at a time
Fast pointer: Moves two steps at a time (or faster)

If there's a cycle, the fast pointer will eventually catch up to the slow pointer. If there's no cycle, the fast pointer will reach the end first.

Visual Representation

Fast & Slow Pointers - Cycle Detection (Floyd's Algorithm)

Floyd's Cycle Detection: Fast pointer moves 2 steps while slow moves 1 step. In a cycle, fast will eventually catch up to slow, proving a cycle exists. Time: O(n), Space: O(1).

Cycle Detection

slow = head
fast = head

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    
    if slow == fast:
        return True  # Cycle detected

return False  # No cycle

Algorithm Section

Cycle Detection Algorithm

function hasCycle(head):
    if head is null or head.next is null:
        return false
    
    slow = head
    fast = head
    
    while fast is not null and fast.next is not null:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return true
    
    return false

Finding Middle Element

function findMiddle(head):
    slow = head
    fast = head
    
    while fast is not null and fast.next is not null:
        slow = slow.next
        fast = fast.next.next
    
    return slow  # slow is at the middle

Implementation in C++

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

bool hasCycle(ListNode *head) {
    if (!head || !head->next) {
        return false;
    }
    
    ListNode *slow = head;
    ListNode *fast = head;
    
    // Fast moves 2 steps, slow moves 1 step
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        // If they meet, there's a cycle
        if (slow == fast) {
            return true;
        }
    }
    
    return false;
}

ListNode* findMiddle(ListNode *head) {
    ListNode *slow = head;
    ListNode *fast = head;
    
    // When fast reaches end, slow is at middle
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;
}

Practice Problems

Problem 1: Linked List Cycle (LeetCode #141)

Given head, the head of a linked list, determine if the linked list has a cycle in it.

Example:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle where the tail connects to the 1st node (0-indexed).

Solution in C++:

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool hasCycle(ListNode *head) {
    if (!head || !head->next) {
        return false;
    }
    
    ListNode *slow = head;
    ListNode *fast = head;
    
    // Fast moves 2 steps, slow moves 1 step
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        // If they meet, there's a cycle
        if (slow == fast) {
            return true;
        }
    }
    
    return false;
}

Step-by-Step Simulation:

Linked List: 3 -> 2 -> 0 -> -4 -> (points back to 2)
Initial: slow=3, fast=3
Step 1: slow=2, fast=0
Step 2: slow=0, fast=2
Step 3: slow=-4, fast=-4
slow == fast, cycle detected!
Why it works: If there's a cycle of length L, and slow is k steps into the cycle when fast enters, fast will catch up to slow in (L-k) steps because fast gains 1 step per iteration.

Explanation: We use Floyd's cycle detection algorithm (also known as the "tortoise and hare" algorithm). The slow pointer moves one step, fast moves two steps. If there's a cycle, fast will eventually catch up to slow. If fast reaches null, there's no cycle. This works because in a cycle, fast gains one step per iteration on slow, so it will eventually catch up. The time complexity is O(n) where n is the number of nodes.

Time Complexity: O(n)

Space Complexity: O(1)

Problem 2: Happy Number (LeetCode #202)

Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat until the number equals 1, or it loops endlessly in a cycle which does not include 1.

Example:

Input: n = 19
Output: true
Explanation: 1² + 9² = 82, 8² + 2² = 68, 6² + 8² = 100, 1² + 0² + 0² = 1

Solution in C++:

#include <iostream>
using namespace std;

int getNext(int num) {
    int total = 0;
    while (num > 0) {
        int digit = num % 10;
        total += digit * digit;
        num /= 10;
    }
    return total;
}

bool isHappy(int n) {
    int slow = n;
    int fast = getNext(n);
    
    // Continue until fast reaches 1 or meets slow (cycle detected)
    while (fast != 1 && slow != fast) {
        slow = getNext(slow);
        fast = getNext(getNext(fast));  // Fast moves 2 steps
    }
    
    return fast == 1;
}

Step-by-Step Simulation (n=19):

Initial: slow=19, fast=getNext(19)=82
Step 1: slow=82, fast=getNext(getNext(82))
getNext(82)=68, getNext(68)=100, fast=100
Step 2: slow=68, fast=getNext(getNext(100))
getNext(100)=1, getNext(1)=1, fast=1
Result: fast==1, return true
Sequence: 19 -> 82 -> 68 -> 100 -> 1

Explanation: We treat the sequence of numbers as a linked list where each number points to the next (via getNext function). We use fast and slow pointers to detect cycles. If we reach 1, it's happy. If slow meets fast before reaching 1, there's a cycle and it's not happy. The fast pointer moves two steps at a time, so if there's a cycle, it will eventually catch up to slow.

Time Complexity: O(log n)

Space Complexity: O(1)

Problem 3: Find the Duplicate Number (LeetCode #287)

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number.

Example:

Input: nums = [1,3,4,2,2]
Output: 2

Solution in C++:

#include <vector>
using namespace std;

int findDuplicate(vector<int>& nums) {
    int slow = nums[0];
    int fast = nums[0];
    
    // Phase 1: Find intersection point in cycle
    do {
        slow = nums[slow];        // Move 1 step
        fast = nums[nums[fast]];   // Move 2 steps
    } while (slow != fast);
    
    // Phase 2: Find entrance to cycle (the duplicate)
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    
    return slow;
}

Step-by-Step Simulation:

Input: nums = [1,3,4,2,2]
Phase 1 - Find Meeting Point:
slow=1, fast=1
slow=nums[1]=3, fast=nums[nums[1]]=nums[3]=2
slow=nums[3]=2, fast=nums[nums[2]]=nums[4]=2
slow=nums[2]=4, fast=nums[nums[2]]=nums[4]=2
slow=nums[4]=2, fast=nums[nums[2]]=nums[4]=2
slow==fast at value 2
Phase 2 - Find Cycle Entrance:
slow=nums[0]=1, fast=2
slow=nums[1]=3, fast=nums[2]=4
slow=nums[3]=2, fast=nums[4]=2
slow==fast at value 2, duplicate found!
Result: 2

Explanation: We treat the array as a linked list where nums[i] points to nums[nums[i]]. The duplicate creates a cycle because two indices point to the same value. First phase: find where slow and fast meet (inside the cycle). Second phase: reset slow to start, move both one step at a time until they meet at the cycle entrance (the duplicate). This works because the distance from start to cycle entrance equals the distance from meeting point to cycle entrance.

Time Complexity: O(n)

Space Complexity: O(1)

Problem 4: Middle of the Linked List (LeetCode #876)

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

Example:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Solution in C++:

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* middleNode(ListNode* head) {
    ListNode *slow = head;
    ListNode *fast = head;
    
    // When fast reaches end, slow is at middle
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;
}

Step-by-Step Simulation:

Linked List: 1 -> 2 -> 3 -> 4 -> 5
Initial: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=5
Step 3: fast->next=nullptr, exit loop
Result: slow points to node 3 (middle)
Why it works: Fast moves 2 steps while slow moves 1 step. When fast has moved n steps (reached end), slow has moved n/2 steps, which is the middle.

Explanation: When fast reaches the end, slow will be at the middle. Fast moves twice as fast, so when fast has moved n steps, slow has moved n/2 steps, which is the middle. This is a classic application of the fast-slow pointer technique. For even-length lists, this returns the second middle node (as per LeetCode problem requirements).

Time Complexity: O(n)

Space Complexity: O(1)

Problem 5: Linked List Cycle II (LeetCode #142)

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

Example:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the 1st node (0-indexed).

Solution in C++:

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* detectCycle(ListNode *head) {
    if (!head || !head->next) {
        return nullptr;
    }
    
    ListNode *slow = head;
    ListNode *fast = head;
    
    // Phase 1: Find meeting point
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            break;  // Cycle detected
        }
    }
    
    // No cycle found
    if (!fast || !fast->next) {
        return nullptr;
    }
    
    // Phase 2: Find cycle entrance
    // Reset slow to head, move both one step at a time
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    
    return slow;  // Cycle entrance
}

Mathematical Proof:

Let:
L = distance from head to cycle start
C = cycle length
X = distance from cycle start to meeting point
When they meet:
Distance traveled by slow = L + X
Distance traveled by fast = L + X + nC (n complete cycles)
Since fast = 2 × slow:
2(L + X) = L + X + nC
L + X = nC
L = nC - X
This means: Distance from head to cycle start = Distance from meeting point to cycle start (going backwards in cycle)

Explanation: First, we detect if there's a cycle using fast-slow pointers. Once they meet, we know there's a cycle. The key insight: the distance from head to cycle start equals the distance from meeting point to cycle start. So we reset slow to head and move both one step until they meet at the cycle start. This is proven mathematically: if slow travels L+X and fast travels 2(L+X) = L+X+nC, then L = nC-X, meaning the distances are equal.

Time Complexity: O(n)

Space Complexity: O(1)