i think you misunderstood the solution.....the process you are trying to do
is divided into three steps
let say the linked list is something like...
------------------------------------
a b | |
| |
| |
|_ _ _ _ _ |
c
where a is the head and b is the point where loop starts.........lets say u
detect the loop at "c" by using slow and fast pointers.....
now.....traverse the loop once more and find the length of the loop say it
is "k".
you can see "k" in two parts - "p" and "q" where, p+q=k and
p is the distance from b to c in anticlockwise direction and,
q is the distance from b to c in clockwise direction,
lets say distance between a to b is "r"
when by traversal from a to c you can calculate q+r....
clearly you know p+q as well as q+r
subtract these two.....you'll get p-r
Case 1) p-r =0 (p==r)
this case is simple both the pointers are at equal distance from
b......hence move both pointer at equal speed....the node at which they
will meet is the start of the loop
Case 2) p-r> 0
move pointer at start by p-r......doing this will make the distance from b
of both the pointers equal...now you can move them with equal speed and
find the start of the loop
Case 3) p-r<0
move pointer at c by r-p ......doing this will make the distance from b of
both the pointers equal.....now you can move them with equal speed and find
the start of the loop
you were not including last 2 cases..........i think i have explained well
enough and it will be clear to you now....
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
<http://gplus.to/amolsharma99>
<http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://youtube.com/amolsharma99>
On Sun, Nov 20, 2011 at 11:42 AM, rahul sharma <[email protected]>wrote:
> when a loop is found then
>
> slow=fast //pointers;
>
> then to find start we move one of any pointer at start and other at same
> palce and move both @ speed of 1...then where they meet is startr,,,
>
>
> can nyone xplain the logic behind this in simple words that how they meet
> at start????thnx in advance
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
