Fast & Slow Pointers — Cycle Detection

What does it solve?

Walk two pointers through a linked list in the same direction: slow advances one node per step, fast advances two. If the list ends, fast falls off into null — no cycle. If there's a loop, fast laps slow and they land on the same node.

Key insight: inside a cycle the gap between fast and slow shrinks by exactly one each step, so a meeting is guaranteed. No hash set, no extra memory — just O(1) space. Same idea powers "find the middle" and "happy number".

The core idea

// two pointers, same direction
slow = head, fast = head
while fast and fast.next:
  slow = slow.next    // +1
  fast = fast.next.next // +2
  if slow == fast:
    return true // cycle
return false     // no cycle

Complexity

Time complexity

O(N)

Slow visits each node at most once. Fast moves twice as fast but travels at most 2N nodes before meeting or exiting. Linear either way.

Space complexity

O(1)

Two pointer variables. No visited-set, no recursion stack. That constant space is the whole reason this beats the hashing approach.

Examples & edge cases

Live animation — tortoise & hare

🐢 slow (+1) 🐇 fast (+2) meeting point → cycle cycle entry (pos)

Linked list — head → … → null / cycle

slow = — fast = — step = — result = —

Step — of —

slow (tortoise)

—

moves +1

fast (hare)

—

moves +2

steps taken

—

pointer advances

Result

—

searching…

Select an example and press Play to start.

✓ Result: —

Speed Medium

Step-by-step table

Step	Phase	slow idx	fast idx	slow val	fast val	Met?	Action

C++ implementation

fast_slow_pointers.cpp

#include <bits/stdc++.h>
using namespace std;

// Singly linked list node
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Floyd's cycle detection — tortoise & hare
bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;        // +1 step
        fast = fast->next->next;  // +2 steps
        if (slow == fast) return true;  // pointers meet → cycle
    }
    return false;                     // fast fell off the end → no cycle
}

// Optional: find the node where the cycle begins (Floyd stage 2)
ListNode* cycleStart(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {            // meeting point found
            ListNode* p = head;
            while (p != slow) { p = p->next; slow = slow->next; }
            return p;                  // entry of the cycle
        }
    }
    return nullptr;
}

int main() {
    // build 3 -> 2 -> 0 -> -4, tail links back to node index 1
    ListNode* a = new ListNode(3);
    ListNode* b = new ListNode(2);
    ListNode* c = new ListNode(0);
    ListNode* d = new ListNode(-4);
    a->next = b; b->next = c; c->next = d; d->next = b; // cycle

    cout << hasCycle(a) << "\n"; // 1 (true)
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars