I know it can be done by using two pointers one slow and other fast. But what is still not clear to me that, If there is a loop then how we can be sure that both slow and fast pointers overlap at a point. I guess there might be some case when they loop infinitely without overlapping. Is there any equation or upper bound on number of cycles in which both must overlap.
1
-
Take a simple example and debug (dryrun) it. You we find it.YoungHobbit– YoungHobbit2015-10-12 20:11:48 +00:00Commented Oct 12, 2015 at 20:11
Add a comment
|
3 Answers
Just forget linked list. And try to assume that you and your buddy is having a race on circular track. But he is faster than you by 2 times. When you have covered half circle, your buddy will have completed full circle, and when you completed the the first circle, your buddy who is 2 time faster will be standing besides you.
Now replace the circle with dots which will represent the nodes of your linked list.
But suppose you don't have circular list, then your buddy who is faster will reach the last node and will finish the race.
4 Comments
Mark Ransom
But if your buddy is skipping two dots each time, he may pass you without you both hitting the same dot at the same time. Do you have an explanation for that?
rici
@MarkRansom: You move first, one dot. Then your buddy moves 2 dots. He can't leap over the dot you are now on because that would require that he was on the dot you were on before, in which case you would already have been on the same dot. (Of course, that's the actual linked list, not the continuous race track proposed here.)
Mark Ransom
@rici which means the description in the question is incorrect, it's not "one slow and one fast" - it's "one +1 and one +2". Arbitrary speeds won't work. I was hoping Ritesh would come back and improve the answer.
rici
@MarkRansom: Fair enough. Ritesh's explanation in the continuous case is correct: there must be a moment in which the two runners are side-by-side. Replacing the continuous motion with discrete steps doesn't change that fact as long as both the tail and the loop are integer multiples of the discrete step length, in which case the two of you will correspond at a discrete step. So arbitrary speeds are fine, but arbitrary lengths are not: the division into dots needs to be integral.
Consider two pointers. P1 and P2. (Tortoise and Hare)
P1 P2 Delta
1 2 1
2 4 2
3 6 3
4 8 4
5 10 5
6 12 6
The distance between the two increases by 1 at each step. Eventually (in a loop) they will meet.
Comments
The idea is that the slow (tortoise) pointer advance 1 item in each step, and the fast (hare) pointer advance 2 items.
When the hare is very close to the tortoise (at X), let say it's 2 items behind (X - 2).. on the next step:
hare position: X
tortoise position: X + 1
And now the hare is just 1 item behind, next step:
hare position: X + 2
tortoise position: X + 2
And they meet. As you can see, if the distance between them was 2 items, they eventually meet, if the distance is 1 item (as is in the following step after 2 items), they will meet on the next step.
The hare is always 1 step faster, so it can't "jump over".
