Can someone explain why after finding the cycle length and then fixing one pointer to the head and another pointer to the kth node from the head and advancing both pointers will result in them meeting at the start of the cycle?
By testing it on a few examples I see that it works, but how would I formally explain to an interviewer why this works for all cases?
Thanks,
tacocat
Hey @tacocat,
You can try to prove it by yourself by setting a variable for cycle length and the length to the start of the cycle. Then you will realize that why it works. Try it first, and let me know if you still have problem.
Version 1.3.2 (This problem is 7.2 in that version): If the slow and fast pointers are set to head (which I’m assuming is not the start of the cycle), and fast is advanced by the length of the cycle, doesn’t it end back at the same node?
Hi @fundou,
That is the solution we have in the book, and basically the idea is to convert this problem into find the k-th last node in a list once you know there is a cycle. That is the reason it works.
Thanks for your prompt reply, @tsunghsienlee!
Sorry, do you imply I shouldn’t have specified this coz its the solution? I’m happy to delete my statement.
What I meant to say is that by doing that, the fast ptr is already at the same position as the slow ptr and now if you advance them one at a time, won’t they always be in sync?
Also, isn’t this (keep one ptr fixed and let the other go around) a simpler solution to detecting the cycle than the fast ptr going twice as fast as the slow one and the (relatively) complicated modulo proof?
Hi @fundou,
I am not very sure what algorithm you meant exactly, we have that in http://elementsofprogramminginterviews.com/solutions/, and you can take a look of that first.
There is no need to delete your statement and I think it is important to making sure you understand what you want to solve.
If you want, we have a newly released judge framework which you can try your algorithm there.