You are viewing a single comment's thread. Return to all comments →
Another explanation using modular arithmetic. Let's assume that:
0
k
n
Then the question is how many iterations i is needed to satisfy the equation
i
i == k + 2i (mod n)
Setting i := n - k we get
i := n - k
n - k (mod n)
k + 2(n - k) = 2n - k == n - k (mod n)
So, we need n - k iteration for two pointers to meet within the cycle.
n - k
Cheers!
Seems like cookies are disabled on this browser, please enable them to open this website
Linked Lists: Detect a Cycle
You are viewing a single comment's thread. Return to all comments →
Another explanation using modular arithmetic. Let's assume that:
0
)k
)n
.Then the question is how many iterations
i
is needed to satisfy the equationSetting
i := n - k
we getn - k (mod n)
k + 2(n - k) = 2n - k == n - k (mod n)
So, we need
n - k
iteration for two pointers to meet within the cycle.Cheers!