CareerCup

I assume the question is about proving that the tortoise - hare approach works ..
I can think of one possible way to prove this, but may be someone can judge how correct I am with this approach -

At any time, we know that the slow pointer would have moved x
The fast pointer would have moved 2x (assuming an increment of 2)

At the point, where these these 2 pointers meet - if they ever do - the fast pointer would have covered the loop (size = k) atleast once or more, or lets use a constant c ( to denote the number of times, the fast pointer has iterated over the loop to meet the slow pointer)

So, we can say that
x + ck = 2x ;
solving for x ,
x= ck ;
We know that x is non zero, so the size of the loop is non zero .. So, the loop exists if the above condition is satisfied ..

Am I right ?

Found Somewhere
2n + 2mi + 2r = n + mj + r (rhs is simply an expression for the faster pointers traversal)
=> n + r = mk (k is another integer)

Me and my Grandfather are walking on the same track. He walks twice faster than me. I move in unit steps.

After my first step, He was ahead of me by one step.

If I met my Grandfather again, then its a necessary and sufficient condition to prove that track is circular in nature.

Else I my Grandfather will find the exit gate and declare that its not circular.

We both must coincide as Grandfather will gain the (total distance + distance traveled by me ) over time as He is twice as faster than me.

Thanks
Ankush

P.S - I am more looking into proof which includes mathematical figures and tell me the exact steps count to determine whether its circular or not?

Whoever runs fast has to hit someone running slower from back (in case of circular track).

So we have following cases with us. Let f-> fast , s->slow. f runs twice fast than s.
we need to check for equality after every move of f and s.

1) f->s
if s moves first...then f moves ...both meets at the same point
if f movies first.. then s movies...both meets at the same point.

2) f->gap->s
here if f moves first then f and s are the same point.
if s moves first then f will move that becomes f->s which is the case one.

With 2 ptrs technique we are always detect the loop.

i have always had this question:

we use two pointers - one that passes though every single element and another that skips every alternate element. is it not possible under any circumstance that, the faster pointer just keeps skipping the position where the slower pointer is stationed and thus doesnt coincide at all?
can somebody please explain?

i tried with a loop with even number of elements and also with odd number of elements...but still not convinced whether the result can be generalized...looking for a concrete proof/explanation..

@aadith: no its not possible. If you skipping every alternate node then still the time taken to reach at every node will be same. Faster node will touch every node. Just think in terms of number theory.

What will happen if we move 2nd pointers by 3? I think it will still find the loop .

Give ur suggestions.

@Aadith...

Here is an attempt to explain with an example..

A --> B --> C --> D --> E --. This is the linked list given to you.
^ |
|--------------------------| it has the loop from E to A.

First pointer moving by one step ,
Second pointer moving by two steps.

Iterations First pointer Second pointer
1 Node A Node B
2 B D
3 C A
4 D C
5 E E

so you found the loop.

Ok Fine..The loop is detected..But I guess this thread was more for fixing the problem and not detecting it..So If any body has the solution for fixing the loop in LinkedList..Pls Share

find the last element in the circular loop (in the same way we find the starting point of the loop) and then set the next pointer of this node to null