Fast and Slow Pointers (Floyd's Cycle Detection)

TL;DR: Run two pointers through a sequence at different speeds: the slow one moves one step, the fast one moves two. If there is a cycle, the fast pointer laps the slow one and they meet inside the loop; if not, the fast pointer falls off the end. The same idea finds the middle of a list (when fast hits the end, slow sits at the midpoint) and locates the cycle entry (reset one pointer to the head and advance both one step at a time). It uses O(1) extra space because all the state lives in two pointers, not a visited set.

The core move: two speeds, one pass

A naive cycle check stores every node you have seen in a hash set and flags the first repeat. That works but costs O(n) memory. Floyd's trick keeps only two pointers. The slow pointer (tortoise) advances one node per step, the fast pointer (hare) advances two. If the list ends, the fast pointer reaches None and there is no cycle. If the list loops back, the fast pointer eventually enters the cycle, circles it, and collides with the slow pointer from behind.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # one step
        fast = fast.next.next       # two steps
        if slow is fast:            # hare lapped the tortoise
            return True
    return False                    # fast fell off the end

Why must they meet? Once both are inside the cycle, look at the gap between them measured in the direction of travel. Each step the fast pointer closes that gap by exactly one (it gains two, slow gains one). A gap that shrinks by one every step inside a finite loop hits zero, so a collision is guaranteed. It cannot "jump over" the slow pointer precisely because the relative speed is one.

Finding the cycle entry

Detecting a cycle is half the battle; interviews often want the node where the loop begins. After the meeting, reset one pointer to the head and move both one step at a time. They meet at the entry.

The arithmetic: let F be the distance from head to the entry and let the slow pointer have traveled F + k into the loop when they meet. The fast pointer went twice as far, so its distance is a whole number of loop lengths ahead. Working it out, the distance from the head to the entry equals the distance from the meeting point to the entry (modulo the loop length). So two pointers, one from the head and one from the meeting point, each moving one step, converge exactly at the entry.

def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                 # phase 1: find a meeting point
            slow = head
            while slow is not fast:      # phase 2: walk to the entry
                slow, fast = slow.next, fast.next
            return slow
    return None

Finding the middle

Same two speeds, no cycle. When the fast pointer runs off the end, the slow pointer has covered exactly half the distance, so it sits on the middle node. This is the standard setup for "reorder a list," "is this a palindrome," and "split a list in two" without a length pre-count.

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow                          # second middle for even length

Why interviewers probe this

This is the classic "can you beat O(n) space" filter. Almost everyone can write the hash-set version; the signal is whether you reach for the pointer trick and, more importantly, whether you can argue the two pointers must collide. The held-back follow-up is nearly always "prove it terminates and meets" or "now return the node where the cycle starts," and the entry-finding proof separates people who memorized the code from people who understand the geometry. A common variant swaps the linked list for a function-iteration sequence (find the duplicate in an array where values index into the array), which is the same algorithm in disguise.

Common misconceptions

• "You need a visited set to detect a cycle." That is the O(n) space version. Two pointers do it in O(1) space.
• "Any speed difference works the same." A relative speed of one guarantees they cannot skip past each other; larger gaps can overshoot and complicate the proof, and the entry-finding arithmetic specifically relies on the 1-and-2 ratio.
• "The meeting point is the start of the cycle." It is not. You meet somewhere inside the loop; you need the second phase (reset to head, step together) to reach the entry.
• "It only works on linked lists." Any sequence with a deterministic next-step works, including array-as-function problems like find-the-duplicate.

Key takeaways

• Two pointers at speeds 1 and 2 detect a cycle in O(1) space; if the list ends, the fast pointer falls off, otherwise they collide inside the loop.
• They must meet because the gap inside the loop shrinks by exactly one each step.
• To find the cycle entry, reset one pointer to the head after the meeting and advance both by one; they converge at the start.
• The same speed-2 setup finds the middle of a list in one pass with no length pre-count.