0

The algorithm uses a fast and a slow pointer to detect a loop in a linked list. My question is, how do I prove that the distance between the point where the two pointers collide in the loop and the start of the loop is equal to the distance between the head of the linked list and the start of the loop?

YSA
  • 799
  • 1
  • 12
  • 30
  • This question is better suited for http://cs.stackexchange.com/ – Ivaylo Strandjev Jan 13 '17 at 14:26
  • Those two distances are not usually the same – Matt Timmermans Jan 13 '17 at 14:37
  • @MattTimmermans if they are not equal, then how would you detect the start of the loop? If you keep incrementing the two pointers by one and the distances aren't equal then that would mean that the pointer that was reset to the head of the linked list is going to enter the loop again. How would you go about it then? – YSA Jan 13 '17 at 14:47
  • That's explained over here: http://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work?rq=1 – Matt Timmermans Jan 13 '17 at 15:21

1 Answers1

-1

Consider the speed of the slow pointer as "x" and the speed of the fast as "2x". Using simple relative motion you can prove that these two will eventually meet if there is a loop.
Now, consider the time being same, so the distance traveled by fast pointer is twice as more than the slow.
If slow travels a distance of a+b then fast will travel a+2b+c. The link will provide you a better understanding.
2*(a+b)=a+2b+c
Solving this equation gives you a=c.
This question already has been answered, you may refer to the link below:
https://cs.stackexchange.com/questions/10360/floyds-cycle-detection-algorithm-determining-the-starting-point-of-cycle

aditya singh
  • 11
  • 3
  • 1
    A link to a solution is welcome, but please ensure your answer is useful without it: [add context around the link](//meta.stackexchange.com/a/8259) so your fellow users will have some idea what it is and why it’s there, then quote the most relevant part of the page you're linking to in case the target page is unavailable. [Answers that are little more than a link may be deleted.](//stackoverflow.com/help/deleted-answers) –  Jul 04 '20 at 15:22
  • I am new here so didn't know about it. Thanks for the comment. – aditya singh Jul 04 '20 at 17:26