Just to reword:
n- handle length
l - loop length
x - total length
p = q = head;
move p by l+1 nodes
then move both p and q 1 node till they meet They will meet at the end
of the handle.
Thanks Vinod.
--~--~-~--~~~---~--~~
You received this message because you ar
Hi.
goal is to find the length of linked list...
there may be cycle in that
my idea is directly trying to find the length instead of finding cycle and doing processing...to find length
traverse the list and hash the addresses..and increment the count untill either u find a null or same a
The loop is at the end as you have said.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send e
I am not sure I got it.
Is the list :
1,2,3,4,5,6,7,8,9,10,11,12,13,8 - i.e the loop is at the end which has
to be the case since node 3 cannot have 2 out links?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Alg
To find the length of the loop:1)You know the node where the two pointers have met.(say NodeX)2)Now make one pointer alone traverse through the loop.(Have a counter which increments for every move)3)It will come back to the same node (NodeX) after making 'length of the loop' jumps
ie the counter g
1. I know there is a cycle
2. Since via the "Hare Tortoise Algo" when the list is detected, the
fast pointer is caught in the loop, we can run it around the loop to
find the length of the cycle.
I don't know the node that has two in-pointers/element that points
backwards
Any ideas now??
I have
Did you detect the exact element that points backwards, or you just
know that there is a cycle somewhere in the list?
(There is a simple and efficient algorithm to know that there is a
cycle without detecting the exact element that points backwards)
--~--~-~--~~~---~-