0

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?

Adeeb HS
  • 139
  • 7
  • 1
    Perhaps this addresses your question? It proves a more general result. https://stackoverflow.com/questions/5130246/why-increase-pointer-by-two-while-finding-loop-in-linked-list-why-not-3-4-5/5130334#5130334 – templatetypedef Jul 16 '22 at 20:57
  • 1
    Does this answer your question? [Why increase pointer by two while finding loop in linked list, why not 3,4,5?](https://stackoverflow.com/questions/5130246/why-increase-pointer-by-two-while-finding-loop-in-linked-list-why-not-3-4-5) – templatetypedef Jul 17 '22 at 14:59

1 Answers1

0

. Let's take an example of odd length linked list.

If you take a linked list loop as 1->2->3->4->5 and 5 is connected to 1(so that it forms a loop). Now, let's have a pointer from node 1 and iterating alternatively through list. Now visiting is done in the following order: 1st iteration: 1->3->5 Next starts from 2. 2nd iteration: 2->4 Next starts from 1... so on...

So, we can observe that every node is visited. This is true even if you start iteration from 2nd node.

. 2nd example of even length, 1->2->3->4->5->6 & 6->1 (cycle). Starting node as 1; Slow => 1, Fast => 2

Slow : 1 ; Fast : 2

Slow : 2 ; Fast : 4

Slow : 3 ; Fast : 6

Slow : 4 ; Fast : 2

Slow : 5 ; Fast : 4

Slow : 6 ; Fast : 6 => Met!

So, in case of odd length, fast meets slow as fast touches every point and in case of even, slow and fast meet at a point after some iterations.

I didn't find proof like thing, but just posted my observations. Any suggestions/corrections are appreciated. :)

Pyata Sandeep
  • 1
  • 1