目次
LeetCode #142
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.
Lemma
$$z = y-x+1 \mod N$$
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$