Two PointersAlgorithmaka Floyd's cycle detection, tortoise and hare, runner technique

Fast & Slow Pointers

Advance one pointer twice as fast as another through a linked structure to find cycles, cycle starts, midpoints, and k-th-from-end nodes in O(1) space.

▶ VisualizePattern: Fast & Slow PointersPractice (3)
Progress

Overview

Fast and slow pointers exploits the fact that in a singly linked list (or any structure where each node has exactly one successor, such as i → f(i)) you cannot index backward or randomly. Two pointers traversing at different speeds still extract global information: whether a cycle exists, where it begins, how long it is, and where the middle of a list lies — all in one or two passes with no extra memory.

Floyd's algorithm is the classic instance: slow moves one step, fast moves two. If fast reaches null, the list is acyclic. If fast ever equals slow, there is a cycle, and a second phase starting a pointer from the head finds the cycle entry. The same trick solves Find the Duplicate Number by treating a[i] as a next-pointer, and finds the middle of a list for Merge Sort on lists and palindrome checks.

linked listcycleO(1) spaceFloydmidpoint

Intuition

A mental model before the formal terms.

Two runners on a track. If the track is a straight road, the faster one simply reaches the end. If the track loops, the faster runner eventually laps the slower one; since it gains exactly one position per step, it cannot jump over the slow runner — it must land on the same spot.

For finding the middle: when the fast walker has covered the whole list at double speed, the slow walker has covered exactly half. No need to count first.

How it works

  1. Set slow = head, fast = head.
  2. Loop while fast and fast.next are non-null: slow = slow.next, fast = fast.next.next.
  3. Cycle detection: if slow == fast inside the loop, a cycle exists. If the loop exits, there is none.
  4. Cycle entry (phase 2): reset p = head; advance p and slow one step each until they meet. That meeting node is the first node of the cycle.
  5. Middle of the list: when the loop exits, slow is at the middle (the second middle for even length; start fast = head.next to get the first middle).
  6. k-th from end: advance fast by k first, then move both by one until fast hits the end; slow is the answer.

Why it works

Meeting is guaranteed inside a cycle. Once both pointers are in the cycle of length C, the gap (fast - slow) mod C shrinks by exactly 1 each step (fast gains 2, slow gains 1). A gap that decreases by 1 each step reaches 0 within C steps — fast cannot skip over slow because it never gains more than one position per step.

Phase 2 finds the entry. Let the tail before the cycle have length μ and the cycle length C. When the pointers meet, slow has taken d steps and fast 2d; both are in the cycle, so the extra d steps fast took must be a whole number of laps: d = k·C. The meeting node is therefore d − μ steps into the cycle. Walking μ further steps from it reaches position d = k·C into the cycle, which is the entry node. Walking μ steps from head also reaches the entry. So a pointer from head and one from the meeting point, moving at the same speed, coincide exactly at the entry.

Middle: after t iterations slow is at index t and fast at 2t; fast stops at index n − 1 or n − 2, so t ≈ n / 2.

Total steps are bounded by μ + C ≤ n per phase, so O(n) time and O(1) space with no visited set.

Recognition

How to tell a problem wants this.

  • "Linked list", "detect a cycle", "return the node where the cycle begins", "without modifying the list", "in O(1) space".
  • "Find the middle of the linked list", "delete the middle node", "check if the linked list is a palindrome", "reorder list" — midpoint is the first step.
  • "Remove the n-th node from the end" in one pass.
  • An array of n + 1 integers in [1, n] with one repeated value and the constraint "do not modify the array, O(1) extra space" — the values form a functional graph i → a[i], and the duplicate is the cycle entry (Find the Duplicate Number).
  • Happy Number and other iterate-a-function-until-repeat problems: the sequence x, f(x), f(f(x)), … is a linked list with a possible cycle.
“cycle in linked list” → Fast & Slow Pointers“reverse a linked list” → Linked List Manipulation

Interactive visualization

Play, step, change the input. ← → and space work too.

headslowfast
1
•
2
•
3
•
4
•
5
•
6
•
7
•
1/10The tail links back to index 3, forming a cycle — but the algorithm does not know that. Start slow and fast at head; fast moves two nodes per step, slow one.
slow (1 step)fast (2 steps)Meeting point / bothCycle start
PseudocodeLearn Fast & Slow Pointers →
1slow = fast = head
2while fast and fast.next:
3  slow = slow.next; fast = fast.next.next
4  if slow == fast: break   # cycle found
5if no meeting: return no cycle
6p = head; while p != slow: p = p.next; slow = slow.next
7return p   # cycle start
Variables
step0
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed

Pseudocode

1slow = fast = head
2while fast != null and fast.next != null:
3  slow = slow.next
4  fast = fast.next.next
5  if slow == fast:            # cycle detected
6    p = head
7    while p != slow:           # phase 2: find the entry
8      p = p.next; slow = slow.next
9    return p
10return null                   # no cycle; slow is now the middle node

Implementations

1# Linked List Cycle II: return the node where the cycle begins, or None
2from __future__ import annotations
3from typing import Optional
4 
5 
6class ListNode:
7    def __init__(self, val: int, next: Optional[ListNode] = None) -> None:
8        self.val = val
9        self.next = next
10 
11 
12def detect_cycle(head: Optional[ListNode]) -> Optional[ListNode]:
131 · Both pointers start at the head
14    slow = head
15    fast = head
162 · Advance slow by 1 and fast by 2 until they meet or fast falls off
17    while fast is not None and fast.next is not None:
18        slow = slow.next
19        fast = fast.next.next
203 · Meeting inside the loop proves a cycle exists
21        if slow is fast:
224 · Phase 2: walk one pointer from head and one from the meeting point
23            p = head
24            while p is not slow:
25                p = p.next
26                slow = slow.next
27            return p  # cycle entry
285 · fast reached the end: no cycle
29    return None
Walkthrough
  1. from __future__ import annotations lets the class reference its own name in type hints without quotes.
  2. while fast is not None and fast.next is not None guards both dereferences; fast.next.next may itself be None, which ends the loop next round.
  3. is compares object identity — the correct test for "same node"; == would fall back to identity here too but reads as value comparison.
  4. Phase 2 walks p from head and slow from the meeting node; they coincide exactly at the cycle entry.
  5. return None is the acyclic case.
Complexity (this implementation)
time O(n) · space O(1)
Language notes
  • Use is / is not for node identity; do not define __eq__ on ListNode or the comparison becomes value-based.
  • Optional[ListNode] and ListNode | None (3.10+) are equivalent; the Optional form works on older interpreters.
  • For the array variant (Find the Duplicate Number) the same loop uses slow = a[slow], fast = a[a[fast]] — no node class needed.
Common mistakes in this language
  • Writing while fast and fast.next is fine for nodes but breaks if a node defines __bool__/__len__; is not None is unambiguous.
  • Comparing slow.val == fast.val.
  • Testing slow is fast before the first move — both start at head, so that would always report a cycle.
Language differences that matter here
  • Node identity: C++ compares raw pointers, JS/TS use === (reference equality), Python uses is. None of them should compare val.
  • Null safety: TS strictNullChecks proves fast.next.next is safe from the loop guard but needs ! on slow; C++ and JS rely entirely on the guard order; Python raises AttributeError on a missed guard.
  • Memory ownership: only C++ has to worry about who frees the nodes; a cyclic list cannot be expressed with unique_ptr and would leak under naive delete traversal.

Complexity

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

At most μ + C steps per phase where μ is the tail length and C the cycle length. A hash set achieves the same in O(n) space.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Cycle detection or cycle-entry in a linked list or in any "next = f(current)" sequence with O(1) memory.
  • Midpoint of a singly linked list without knowing its length (split for merge sort, palindrome check, reorder).
  • k-th node from the end in one pass.
  • Duplicate detection in a read-only array of values in [1, n] (functional graph view).
Avoid it when
  • Random-access arrays where you simply want the middle — use n / 2.
  • General graphs with branching — Floyd needs exactly one successor per node; use Cycle Detection with DFS colors instead.
  • When you also need every visited node (e.g. to remove the cycle and keep the list) and memory is not constrained — a Hash Set is simpler and equally fast.
  • Doubly linked lists with a known tail — walking from both ends may be clearer.

Alternatives

Hash SetCycle DetectionTwo Pointers (Same Direction)

Common mistakes

  • Checking fast.next.next without first checking fast.next is non-null — null dereference on even-length acyclic lists.
  • Comparing node *values* instead of node *identity* when testing slow == fast.
  • Starting slow and fast at different nodes and then treating the first comparison as a meeting (or initializing both at head and testing equality before moving).
  • Off-by-one on the midpoint: fast = head yields the second middle for even lengths; fast = head.next yields the first. Pick deliberately for splitting.
  • For Find the Duplicate Number, starting the walk from index 0 is essential because 0 is never a value, so it is guaranteed to be outside the cycle.

Interview patterns

  • Linked List Cycle I/II: detect, then find the entry node.
  • Middle of the Linked List → Palindrome Linked List (find mid, reverse second half, compare).
  • Remove N-th Node From End with a dummy head and a k-gap between pointers.
  • Find the Duplicate Number as cycle entry in the functional graph i → nums[i].
  • Happy Number: detect whether the digit-square sequence loops without reaching 1.
  • Sort List: fast/slow split plus Merge Sort.
Interview questions on this

Example problems

Linked List CycleeasyMiddle of the Linked ListeasyFind the Duplicate Numbermedium