Cycle start point in linked list
How does moving the tortoise to the beginning of the linked list, while keeping the hare at the meeting place, followed by moving both one step at a time, make them meet at starting point of the cycle?
Discussion :
We can easily understand this from below diagram :
S - the non-loop part of the list
X - the point where slow and fast pointers meet
When two pointers are meet, slow pointer traveled S+X.
what about the fast pointer?
There are two ways to think about it.
1. Fast pointer traveled twice as much as slow pointer, which is 2*(S+X)
2. Fast pointer traveled the same distance as slow pointer plus the distance of loop L, which is (S+X)+L
This is interesting, because if you put these two together, 2*(S+X) = (S+X)+L
simply it to S+X=L, which means S+X equals to the distance of the loop L.
Therefore, at position X in the loop, keep moving S distance, then you are guaranteed to meet the start of the loop.
Hope this helps :)
Discussion :
We can easily understand this from below diagram :
S - the non-loop part of the list
X - the point where slow and fast pointers meet
When two pointers are meet, slow pointer traveled S+X.
what about the fast pointer?
There are two ways to think about it.
1. Fast pointer traveled twice as much as slow pointer, which is 2*(S+X)
2. Fast pointer traveled the same distance as slow pointer plus the distance of loop L, which is (S+X)+L
This is interesting, because if you put these two together, 2*(S+X) = (S+X)+L
simply it to S+X=L, which means S+X equals to the distance of the loop L.
Therefore, at position X in the loop, keep moving S distance, then you are guaranteed to meet the start of the loop.
Hope this helps :)
Comments
Post a Comment