Why increase pointer by 2 while finding loop in a linked list, why not 3,4 or 5?
In Floyd's cycle-finding algorithm , Its mentioned that we have to take 2 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.
But the question is why we increase faster pointer by 2. Why not something else?
Discussion :
We can answer this question with a simple proof.
Let us suppose the length of the list which does not contain the loop be S, length of the loop be T and the ratio of fast pointer speed to slow pointer speed be K.
Let the two pointers meet at a distance J from the start of the loop.
So, the distance slow pointer travels = S+J. Distance the fast pointer travels = S+J+M*T (where M is the number of times the fast pointer has completed the loop). But, the fast pointer would also have traveled a distance K*(S+J) (K times the distance of the slow pointer).
Therefore, we get K*(S+J) = S+J+M*T
S+J= (M/K-1)*T
Hence, from the above equation, length the slow pointer travels is an integer multiple of the loop length.
For greatest efficiency , (M/K-1) = 1 (the slow pointer shouldn't have traveled the loop more than once.)
Therefore , M=K-1 => K=M+1
Since M is the number of times the fast pointer has completed the loop, M>=1 . For greatest efficiency, M=1.
Therefore K = 2.
If we take a value of K > 2 , more the distance the two pointers would have to travel.
Hope this explanation helps :)
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.
But the question is why we increase faster pointer by 2. Why not something else?
Discussion :
We can answer this question with a simple proof.
Let us suppose the length of the list which does not contain the loop be S, length of the loop be T and the ratio of fast pointer speed to slow pointer speed be K.
Let the two pointers meet at a distance J from the start of the loop.
So, the distance slow pointer travels = S+J. Distance the fast pointer travels = S+J+M*T (where M is the number of times the fast pointer has completed the loop). But, the fast pointer would also have traveled a distance K*(S+J) (K times the distance of the slow pointer).
Therefore, we get K*(S+J) = S+J+M*T
S+J= (M/K-1)*T
Hence, from the above equation, length the slow pointer travels is an integer multiple of the loop length.
For greatest efficiency , (M/K-1) = 1 (the slow pointer shouldn't have traveled the loop more than once.)
Therefore , M=K-1 => K=M+1
Since M is the number of times the fast pointer has completed the loop, M>=1 . For greatest efficiency, M=1.
Therefore K = 2.
If we take a value of K > 2 , more the distance the two pointers would have to travel.
Hope this explanation helps :)
Comments
Post a Comment