CODEWITHSUNDEEP
algorithmsingly-linked-list
spider
spider

Reputation: 21

How loop detection algorithm in linked list works

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.

Upvotes: 2

Views: 49

Answers (3)

Michael Y.
Michael Y.

Reputation: 661

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.

Upvotes: 1

Amit
Amit

Reputation: 46323

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".

Upvotes: 0

Ritesh
Ritesh

Reputation: 1847

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.

Upvotes: 1

Related Questions