DSA Roadmap/Two Pointers

Fast & Slow Pointers

Run one pointer twice as fast as the other to find midpoints and detect cycles in O(1) space — no hash set required.

!!2/5Theory: 1h 30m6 problems

What the pattern actually is

Fast & slow pointers (Floyd's Tortoise and Hare) start both pointers at the same place and advance them at different speeds — canonically, the slow pointer moves one step per iteration and the fast pointer moves two. This is fundamentally different from opposite-direction two pointers: there's no "sortedness" precondition here, because the structure you're walking is a chain of successors (a linked list's next pointers, or any sequence defined implicitly by a function next(x)), not a random-access array with two ends.

Related (linked lists only): when both pointers move at the same speed but one gets a head start of k nodes (fixed-gap / k-offset), that's a different template — used for "nth from end" and rotation split points. See Linked List → Core Linked List Techniques for the full treatment; this page covers the 1:2 speed-ratio variant.

Recognize this pattern when you see:

  • Linked list problems mentioning cycles ("does it loop back on itself?").
  • Linked list problems asking for the middle node without two passes or a length count.
  • Any problem where you can model the input as a functional graph — every element deterministically points to exactly one "next" element (an index pointing to arr[index], or a number mapping to the sum of the squares of its digits). If a finite set of states each has exactly one successor, iterating it forever must eventually cycle — this is the pigeonhole principle, and it's the tell that Floyd's algorithm applies even outside linked lists.
  • Constraints like O(1) extra space on a problem a hash set would otherwise solve trivially in O(n) space. This "can you do it without extra memory?" follow-up is the single most common reason interviewers reach for this pattern.

Mechanics: three things this pattern actually does

1. Finding the middle. Advance slow by 1 and fast by 2. When fast (or fast.next) hits the end, slow is at the middle.

def find_middle(head): slow, fast = head, head while fast and fast.next: slow = slow.next fast = fast.next.next return slow # for even length, this lands on the second of the two middle nodes

Note the two while conditions: fast guards against starting on an empty list, fast.next guards against reading past the last node. Getting this pair of null-checks wrong is the #1 source of NoneType has no attribute 'next' crashes in this pattern.

2. Detecting a cycle. Same loop, but you also check whether slow and fast have become the same node — if the list has a cycle, the fast pointer can never simply "escape" past the slow pointer without landing on it first (it closes the gap by exactly one node per iteration once both are inside the cycle), so they are guaranteed to meet within one full loop of the cycle.

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

3. Finding where the cycle starts (the two-phase algorithm). This is the part most candidates memorize without understanding, which falls apart under interviewer follow-up questions. The setup: let the tail leading into the cycle have length a, let the cycle have length c, and let the meeting point from phase 1 be b steps into the cycle (measured from the cycle's start, in the direction of travel).

  • Phase 1: run slow/fast as above until they meet. At that point, slow has traveled a + b steps; fast has traveled 2(a + b) steps; and the extra distance fast covered, a + b, must be a whole number of laps around the cycle, so a + b ≡ 0 (mod c), i.e. a ≡ -b ≡ (c - b) (mod c).
  • Phase 2: reset one pointer to head, leave the other at the meeting point, and advance both by one step at a time. The one that started at head needs exactly a steps to reach the cycle start; the one that started at the meeting point needs exactly c - b steps to also reach the cycle start (looping around if needed) — and phase 1's arithmetic just showed those two quantities are congruent mod c. So they meet exactly at the cycle's entrance.
def find_cycle_start(head): slow, fast = head, head while fast and fast.next: slow, fast = slow.next, fast.next.next if slow is fast: break else: return None # fast ran off the end: no cycle ptr = head while ptr is not slow: ptr, slow = ptr.next, slow.next return ptr # the first node of the cycle

You don't need to reproduce the modular-arithmetic proof from memory in an interview, but you should be able to state the shape of it ("the distance to the cycle start equals the distance from the meeting point back to the cycle start, modulo the cycle length — so resetting one pointer to head and walking both at speed 1 makes them meet exactly there"). That's the difference between having memorized a template and understanding an algorithm.

Complexity — and why it beats the hash-set approach

  • Time: O(n). Phase 1 takes at most O(n) steps: if there's no cycle, fast reaches the end in at most n/2 iterations; if there is one, the argument above bounds the meeting time by one full traversal of the tail plus one lap of the cycle, both of which are ≤ n. Phase 2 is bounded by a ≤ n steps. Total: O(n), same asymptotic class as the naive "store every visited node in a hash set" approach.
  • Space: O(1). This is the entire point of the pattern — it gets the same O(n) time as the hash-set method while using two pointer variables instead of an O(n) set. Whenever an interviewer asks "can you avoid the extra space?" on a linked-list or sequence problem, fast & slow pointers is very often the answer they're fishing for.

Pitfalls and interview gotchas

  • Null-pointer checks in the wrong order or missing entirely. Always check fast and fast.next (in that order — short-circuit evaluation matters) before dereferencing fast.next.next.
  • Off-by-one on "the middle" for even-length lists. Starting fast at head vs. head.next changes whether slow lands on the first or second of the two middle nodes for even-length inputs. Decide which one your problem needs before coding, and state the choice explicitly.
  • Using == vs. identity for the meeting check on custom objects — for linked list nodes you want reference identity (is in Python, reference equality in Java/C++), not value equality, since two different nodes could coincidentally hold equal values.
  • Applying it where there's no well-defined single successor. Fast & slow pointers require exactly one deterministic "next" per state. It does not directly apply to, say, a tree (which has multiple children) or a graph with branching — those need BFS/DFS instead.
  • Forgetting the array-as-functional-graph trick. A very common senior-level twist is a problem that looks like a plain array/integer problem but is secretly a linked-list-cycle problem in disguise: if every index deterministically maps to another index (or every number maps to another number via some rule), you can run Floyd's algorithm over that implicit graph without building any real pointers.
  • Conflating "has a cycle" with "is entirely cyclic." Some problems (especially the array-based ones) require the cycle to have length > 1, or to consist of moves all in the same direction — read the exact cycle definition in the problem statement instead of assuming the plain linked-list version applies unchanged.

Illustration: cycle detection over an abstract successor function

The version below makes explicit that this pattern only depends on a step function, not on ListNode objects — the same code detects a cycle in a linked list, in a functional graph encoded as an array, or in any other deterministic chain, as long as you supply the right step.

def phase1_find_meeting_point(start, step): slow = fast = start while True: slow = step(slow) fast = step(step(fast)) if slow == fast: return slow # In a domain with a guaranteed sentinel "no next" value (e.g. None), # you would also break out here if step(fast) hits that sentinel.

Swap in step = lambda node: node.next for a linked list, or step = lambda i: arr[i] for an array read as a functional graph, and the meeting-point logic is identical — only the surrounding null/bounds handling changes per domain.

When to use fast/slow vs. the rest of the two-pointer family

PatternPointer movementPreconditionTypical signal
Fast & slow (this page)Same start, different speeds (1:2)Deterministic single-successor chain"cycle," "middle of a linked list," "detect a repeat without extra space"
Fixed-gap (linked lists)Same speed, k nodes apart after head startSingly linked list, no random access"nth from end," "rotate right by k" — see Linked List topic
Opposite-direction (previous page)Converge from both endsSorted / monotonic, random access"sorted array," "pair/triplet sum," "palindrome"
Sliding window (next topic)Both move forward, window grows/shrinksContiguous range matters, random access"longest/shortest subarray/substring satisfying..."

The dividing line between fast/slow and the other two is structural, not stylistic: fast/slow shows up wherever you cannot jump directly to an arbitrary position (a linked list, or a sequence only defined by repeatedly applying a function) and therefore cannot use two ends or a shrinking window — you can only ever ask "what's next?"

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.