Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Why this work?

umesh

May 9, 2025

Let:

  • l = distance from head to start of cycle
  • m = distance from start of cycle to meeting point of fast and slow pointer
  • k = length of the cycle
  • This gives, k - m = distance from meeting point to start of cycle

When fast and slow meet inside the cycle:

slow distance = l + m fast distance = l + m + n·k (some multiple of the cycle)

Since fast moves twice as fast:

2(l + m) = l + m + n·k → l + m = n·k

From this:

l = n·k - m = (k - m) (mod k)

This means:

  • Distance from head to start of cycle and met point to start of the cycle are same.
  • So, if you start one pointer at head and the other at meeting point,
  • And move both 1 step at a time, they will cover same distance and meet at the start of the cycle for the first time.

1

0

Comments
Comments