LeetCode #142

Linked List Cycle II

This $O(n)$ solution is not intuitional. I proved using modulo arithmetic.

Proof

Let $x$ be the index of the node where fast pointer and slow pointer meets.
Let $y$ be the index of the tail.
Let $z$ be the index of the node that tail's next pointer is connected to.

Proof.

From the definition of $x$:
$2x-x =x= 0 \mod N$
From the definition of $y$ and$z$:
$y-z+1=N$
Therefore, $x=N=y-z+1 \mod N$