Fast & Slow Pointers

    DSA · Intermediate

    Definition

    Two pointers move at different speeds to detect cycles or find middles.

    Solves linked-list cycle, middle node and happy number problems.

    Diagram

    slow →fast →→meet in loop

    Flowchart

    slow moves 1fast moves 2If they meet → cycleIf fast ends → no cycle

    Example: Happy number

    def nxt(n): return sum(int(d) ** 2 for d in str(n))
def happy(n):
    s, f = n, nxt(n)
    while f != 1 and s != f:
        s, f = nxt(s), nxt(nxt(f))
    return f == 1
print(happy(19), happy(2))

    Output: True False

    Complexity

    O(n) time · O(1) space

    Key points

    • Floyd's cycle detection
    • Find cycle start by resetting one pointer to head

    Interview questions

    How to find where the cycle starts?

    After meeting, move one pointer to head; advance both by 1 until they meet.

    More DSA topics

    ArraysLinked ListStackQueue