Dashboard/Coding patterns/02. Fast and Slow Pointers

CODING PATTERNS · LESSON 2 OF 28 · 32 MIN VIDEO · 10 PROBLEMS

Fast and Slow Pointers

Module Progress (0 / 10 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (32 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Fast and Slow Pointers — How the Pattern Works

The Fast and Slow Pointers pattern (Floyd's Tortoise and Hare algorithm) traverses a linked structure or deterministic state-transition graph using two pointers advancing at a fixed 2:1 speed ratio: slow steps 1 link per iteration while fast steps 2 links. In an acyclic chain of length n, fast reaches the end after floor(n / 2) iterations, leaving slow positioned at the exact midpoint in a single pass. In a cyclic chain, once both pointers enter the cycle, fast reduces the modular backward gap to slow by 2 - 1 = 1 node per step, guaranteeing collision inside the cycle without skipping over slow and reducing O(n) hash-set space or multi-pass counting to O(n) time and O(1) auxiliary space.

WHEN TO USE THIS PATTERN
  • Singly or circular linked list problems asking to detect a cycle, compute cycle length, remove a cycle, or locate the middle node using O(1) extra memory.
  • Symmetric linked list operations (palindrome check, maximum twin sum, list folding) where locating the midpoint enables reversing the second half in place.
  • Implicit functional graphs where every state x deterministically maps to one next state f(x) (such as digit-square sums or modular jump arrays (i + nums[i]) % n), reducing state repetition to cycle detection.
  • Read-only array duplicate problems with n + 1 integers in [1, n], where treating values as next-index pointers (i -> nums[i]) maps the duplicate number to a cycle's entrance node.
COMMON INTERVIEW PITFALLS
  • Dereferencing fast.next.next without guarding while fast and fast.next: first, causing a null-pointer AttributeError on empty lists or odd/even list tails.
  • Comparing slow.val == fast.val instead of object identity slow is fast on linked list nodes, which triggers false-positive collisions whenever distinct nodes hold equal values.
  • Misaligning the midpoint on even-length lists: starting slow = fast = head stops slow on the second middle node (index n // 2), whereas splitting into two disjoint lists requires stopping at index (n // 2) - 1.
  • Accepting 1-node self-loops or mixed-direction edges in circular array problems instead of verifying slow != step(slow) and uniform jump signs (sign * nums[x] > 0).
Floyd's Two-Phase Cycle Detection & EntranceDetect whether a linked list or functional graph contains a cycle, and optionally recover the exact node where the cycle starts in O(1) space.
def detect_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None
Single-Pass Midpoint & In-Place Second-Half ReversalFind the middle node of an acyclic linked list (second middle on even lengths) and reverse the back half in place for symmetric comparison.
def reverse_second_half(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    prev = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev, slow = slow, nxt
    return prev
🔒 PRO PROBLEMTarget: O(n) time · O(1) space

10. Linked List Cycle IV

Pattern Trigger: where a loop starts → meet, then restart at head

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

Inside the loop, how many nodes does fast gain on slow with each step?