Fast & Slow Pointer

Finding middle, cycle detection, and cycle start node.

7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Cycle Detection (Floyd's Algorithm)

Slow moves 1 step, fast moves 2 steps. If there's a cycle, they will meet. If fast reaches nil, no cycle.

Gocycle-detection.go

12 linesLn 1, Col 1Go

Fast pointer laps slow pointer if cycle exists. If no cycle, fast hits end. O(n) time, O(1) space.

Finding Middle Element

When fast reaches end, slow is at middle. For even length, returns second middle. For first middle, check fast.Next.Next != nil.

Gofind-middle.go

19 linesLn 1, Col 1Go

Distance traveled: slow = n/2, fast = n. When fast at end, slow at middle. Adjust fast condition for first vs second middle.

Finding Cycle Start

After detecting cycle (slow == fast), reset slow to head. Move both 1 step at a time. They meet at cycle start.

Gofind-cycle-start.go

20 linesLn 1, Col 1Go

Phase 1 finds meeting point. Phase 2: distance from head to cycle start = distance from meeting point to cycle start (modulo cycle length).

Why It Works (Proof)

Let a = distance from head to cycle start, b = distance from cycle start to meeting point, c = cycle length - b. When they meet: slow traveled a + b, fast traveled a + b + k(a+b) where k is laps. Since fast = 2*slow: 2(a+b) = a+b+kc → a = kc - b = (k-1)c + c - b. So a ≡ c-b (mod c). Moving slow to head, both 1 step, they meet after a steps at cycle start.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.