141. Linked List Cycle

• 141. Linked List Cycle
  • Intuition
  • Proof
    • Why walker and runner will meet
    • Why the speed of fast should be twice of the slow one
    • How to find the Cycle length
    • How to find the start point
  • Solution

Intuition

If a walker(slow) and runner(fast) on a cycle, sooner or latter, they will meet each other.

Proof

Why walker and runner will meet

• Denote C as the cycle length.
• Denote L as the leading segement.

When the walker enters the cycle, the runner has already been L % C. Thus, runner needs run more than (C - L % C) + (k * C), where k ∈ [0, +∞) and the (C - L % C) + (k * C) must be the multiple of speed difference.

Why the speed of fast should be twice of the slow one

如果 k 是倍数，

steps = ((C - L % C) + kC) / (k - 1)
      = (2C - L % C) / (k - 1) + C

How to find the Cycle length

Store where the point is, use another one to walk until they meets.

How to find the start point

Solution

Update Code