2021/12/04 15:50 更新
68 いいね ブックマーク

# 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$

ピックアップ
コメント