2021/12/04 15:50 更新
Linked List Cycle II
72 いいね ブックマーク

LeetCode #142

Linked List Cycle II

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

Proof

Let xx be the index of the node where fast pointer and slow pointer meets.
Let yy be the index of the tail.
Let zz be the index of the node that tail's next pointer is connected to.

Lemma
z=yx+1mod  Nz = y-x+1 \mod N

Proof.

From the definition of xx:
2xx=x=0mod  N2x-x =x= 0 \mod N
From the definition of yy andzz:
yz+1=Ny-z+1=N
Therefore, x=N=yz+1mod  Nx=N=y-z+1 \mod N