Why increase pointer by two while finding loop in linked list, why not 3,4,5?

Posted by GG on Stack Overflow See other posts from Stack Overflow or by GG
Published on 2011-02-26T22:50:46Z Indexed on 2011/02/27 7:24 UTC
Read the original article Hit count: 220

I had a look at question already which talk about algorithm to find loop in a linked list. I have read Floyd's cycle-finding algorithm solution, mentioned at lot of places that we have to take two pointers. One pointer( slower/tortoise ) is increased by one and other pointer( faster/hare ) is increased by 2. When they are equal we find the loop and if faster pointer reaches null there is no loop in the linked list.

Now my question is why we increase faster pointer by 2. Why not something else? Increasing by 2 is necessary or we can increase it by X to get the result. Is it necessary that we will find a loop if we increment faster pointer by 2 or there can be the case where we need to increment by 3 or 5 or x.

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about data-structures