Slow and Fast Pointers

Commonly used to detect cycles or find the middle of a list.

1. Template

int fn(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    int ans = 0;

    while (fast != nullptr && fast->next != nullptr) {
        // do logic
        slow = slow->next;
        fast = fast->next->next;
    }

    return ans;
}

2. Detect Cycles, LeetCode 141

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

// Example: Detecting a cycle in a linked list using fast and slow pointers
bool hasCycle(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return false;

    ListNode* slow = head;
    ListNode* fast = head->next;

    while (slow != fast) {
        if (fast == nullptr || fast->next == nullptr) return false;
        slow = slow->next;
        fast = fast->next->next;
    }

    return true;
}

3. Find the Middle of a Linked List, LeetCode 876

Problem: 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.

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

4. Happy Number, LeetCode 202

A number is considered happy if repeatedly summing the squares of its digits leads to 1. If it enters a cycle that doesn’t include 1, it’s not a happy number.

int sumOfSquares(int n) {
    int sum = 0;
    while (n) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}

bool isHappy(int n) {
    int slow = n;
    int fast = sumOfSquares(n);

    while (fast != 1 && slow != fast) {
        slow = sumOfSquares(slow);
        fast = sumOfSquares(sumOfSquares(fast));
    }

    return fast == 1;
}