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