I have access to fast internet only for this weekend, so let me clear all my doubts..
I have a singly linked list with unique satellite data in each node.. Its given that there is a possibility of a loop in it..
The first part of the question is to check if there is a loop or not..
The next part is to find out where the loop actually starts..
For the first part, we can use "fast pointer - slow pointer " method and its pretty trivial..For the second part.. I could think of an algorithm which is O(n*2)
wherein,
one pointer p : is pointing to the head of the ll,
another pointer q : is pointing to the node where the fast and the slow pointers met in the first part..
In each iteration :
p moved to the next node ,
q is made to go around the loop till it returns to the point where it started,
chaeck if p an q point to the same node .. If they do, then that is the point where the loop starts, else continue
This is too inefficient.. Can some one suggest a better algo?
