Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/15 done
  • Fast & Slow Pointers
  • In-Place List Reversal
Learn/Data Structures & Algorithms/Linked Lists

Fast & Slow Pointers

7 min Beginner 8 steps

Detect cycles and find middles with two speeds.

Steps
0
Reached null
never
Visited set
1 nodesO(n) space
123456curr
current visited done
In this lessonStep 1 of 8
  1. The problem
  2. Two speeds
  3. Detect
  4. Why meet
  5. Cycle start
  6. The math
  7. Middle
  8. Recap
Step 1 / 8problem

A list that never ends

Walk this list one node at a time and you never reach null: node 6 points back to 3.

A hash set of visited nodes would catch it, but costs O(n) space. The problem asks for O(1).

Key idea

Cycle, loop, middle or "kth from the end" with O(1) space: think fast and slow pointers.

←→ step·R replay·Space pause

You'll learn

  • Detect a cycle in O(1) space with two speeds
  • Explain why the pointers must meet
  • Find where the cycle starts with a second phase
  • Derive F = n·C - a
  • Pick the loop condition for the first or second middle
Read the full notesArrays and Linked Lists, 4