I've seen several proofs for Floyd's algorithm in several posts inside and outside stack overflow. All of them proves the second part of the algorithm that is, why the method to find the start of the cycle works. But none of the proofs I've seen addresses the first part that is, why the slow pointer and the fast pointer will meet inside the loop. Why wouldn't the slow and the fast pointer go on infinity and never meet at a particular node? All the proofs I've seen so far either do not address this or tells "it's obvious" that the pointers will meet. I'm sorry but I don't get why the points will never go on an infinite loop, to me this feels like the proof of Fermat's last theorem. Can someone prove why it'll always meet for a loop of any length?
I'm not sure if the concept is similar but the fact that two pointers will meet in a loop seems similar this question :
Suppose three friends A , B and C covers the periphery of a closed path in 2 , 4 ,6 minutes respectively. When they will meet again ?
the answer is LCM(2,4,6) = 12 minutes. I don't have concrete mathematical proof but I hope it helps.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With