Linked List Cycle II

Notation:

1. From head to cycleStartPoint:  a
2. From cycleStartPoint to encounter point: b
3. Number of nodes in in cycle: r
4. Total length of the list: L

First step: start fast runner and slow runner, stop when then encounter each other.

• slower runner move:  s = a + b; (eq1)
• fast runner move: S = 2s = s + kr; (eq2)

      From eq1 and eq2, we can get: s = kr = a + b;

• From kr = a + b
• (k-1)r + r = a + b
• (k-1)r + (L - a) = a + b
• (k-1)r + (L - a - b) = a

So: a = (k-1) cycles + (distance between encounter-point and cycle-start-point)

Step2: Move fast runner to head. Start both fast-runner and slow-runner, both move one node each step.

They will encounter each other again at cycle-start-point.