Fast and Slow Pointers — Floyd's Cycle Detection Explained

Q: Why does resetting one pointer to the head find the cycle's start?

With a = head to entry, b = entry to meeting point and c = the rest of the loop, the meeting gives 2(a + b) = a + b + k(b + c), so a = k(b + c) - b. The distance from the head to the entry equals the distance from the meeting point round to the entry, so two pointers moving one step at a time from those two points arrive together.

Also called Floyd's tortoise and hare. Two pointers walk the same structure at different speeds; what you learn from where they meet answers a surprising range of questions. The pattern's real selling point is space: it does in O(1) what the obvious hash-set solution does in O(n), and "can you do it without extra space" is the standard follow-up.

The idea

slow advances one step per iteration, fast advances two.

If the structure ends, fast reaches the end first — and slow is exactly halfway.
If the structure has a cycle, fast cannot escape, laps slow, and they meet.

The second point is the one worth being able to justify. Once both pointers are inside the loop, fast closes the gap to slow by exactly one node per iteration. A gap that shrinks by one every step and lives in a finite loop must reach zero — so they always meet, and never step over each other.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;   // reference identity, not equals()
    }
    return false;
}

bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;   // pointer identity
    }
    return false;
}

bool hasCycle(struct ListNode* head) {
    struct ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;   /* pointer identity */
    }
    return false;
}

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;   // identity, not deep equality
  }
  return false;
}

Finding where the cycle starts

The part people memorise without understanding. After the meeting, reset one pointer to the head and advance both one step at a time; they meet at the cycle's entry node.

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow
    return None

ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            slow = head;                    // reset one pointer to the head
            while (slow != fast) {          // now advance BOTH by one
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = head;                    // reset one pointer to the head
            while (slow != fast) {          // now advance BOTH by one
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;
}

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = head;                    /* reset one pointer to the head */
            while (slow != fast) {          /* now advance BOTH by one */
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return NULL;
}

function detectCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      slow = head;                   // reset one pointer to the head
      while (slow !== fast) {        // now advance BOTH by one
        slow = slow.next;
        fast = fast.next;
      }
      return slow;
    }
  }
  return null;
}

At the meeting point 2(a + b) = a + b + k(b + c), so a = k(b + c) − b — the head and the meeting point are the same distance from the entry.

Why it works. Let a be the distance from head to the cycle entry, b the distance

from the entry to the meeting point, and c the rest of the loop. When they meet, slow has walked a + b and fast has walked a + b + k(b + c) for some number of laps k. Fast walked exactly twice as far, so 2(a + b) = a + b + k(b + c), which simplifies to a = k(b + c) - b. That is: the distance from the head to the entry equals the distance from the meeting point to the entry (plus whole laps). So two pointers walking one step each from those two places arrive together.

Where else it applies

Question	The trick
Middle of a linked list	When `fast` hits the end, `slow` is the middle
Nth node from the end	Start `fast` `n` nodes ahead, then move both at speed 1
Happy Number	Digit-square-sum is a function, so iterating it is a linked list — cycles mean unhappy
Find the Duplicate Number	Treat `i → nums[i]` as a linked list; the duplicate is the cycle entry
Palindrome Linked List	Find the middle, reverse the second half, compare

Find the Duplicate Number is the one to actually understand. An array of n + 1 values

in [1, n] defines a function from index to index. Repeated values mean two indices point to the same place, which is exactly a cycle entry — so the answer is detect_cycle on an array, in O(1) space, without modifying the input. That constraint combination is unreachable any other way, which is why it gets asked.

Complexity

O(n) time, O(1) space. In the cyclic case both pointers make at most a constant number of passes over the loop before meeting.

Mistakes that cost the round

Wrong null guard. while fast and fast.next — checking only fast crashes on

fast.next.next at the last node of an even-length list.

Starting them apart. slow = head; fast = head.next also works for pure detection

but breaks the entry-point maths above, which assumes both start at the head.

Off-by-one on "the middle". With both starting at the head, an even-length list

leaves slow on the second middle node. Start fast one ahead to get the first.

Comparing values, not nodes. slow == fast on nodes with equal payloads is a false

positive. Compare identity.

What to drill

Linked List Cycle — the detection loop.
Middle of the Linked List — same skeleton, different question.
Happy Number — the pattern applied to a number sequence.
Linked List Cycle II — the entry point, with the proof above.
Find the Duplicate Number — the array-as-linked-list reframe.
Palindrome Linked List — composing find-middle with reversal.

All on the 22 DSA Patterns sheet.

Frequently asked

Why do fast and slow pointers always meet in a cycle?

Once both are inside the loop, the fast pointer closes the gap to the slow one by exactly one node per iteration, since it moves two steps to the slow pointer's one. A non-negative gap that shrinks by exactly one each step must hit zero, and because it shrinks by one it can never jump past zero — so they land on the same node.

Why does resetting one pointer to the head find the cycle's start?

With a = head to entry, b = entry to meeting point and c = the rest of the loop, the meeting gives 2(a + b) = a + b + k(b + c), so a = k(b + c) - b. The distance from the head to the entry equals the distance from the meeting point round to the entry, so two pointers moving one step at a time from those two points arrive together.

When should I use a hash set instead?

When you need more than the fact of a cycle — the full set of visited nodes, or a per-node count. A hash set is O(n) space but simpler and easier to extend. Fast and slow is the answer when the question says constant space or forbids modifying the input.

Fast and Slow Pointer