@Ravi:
Count the nodes in the loop.
Step one point that many nodes into the list.
Start another pointer at the head.
Step both pointers until the two "next" pointers are equal.
Now you have the two nodes which have the same "next" pointer.
Don
// Returns NULL if there is no loop
// Returns pointer to last node before the loop if there is a loop
Node *FindLoop(Node *head)
{
Node *p1=head, *p2=head;
while(p2)
{
p2 = p2->next;
if (p2) p2 = p2->next;
p1 = p1->next;
if (p1 == p2) break;
}
if (!p2) return 0;
// Count nodes in loop
int count = 1;
for(p2=p1->next; p2 != p1; p2 = p2->next)
++count;
// Start p1 at head and p2 at position count
p1 = p2 = head;
for(int i = 0; i < count; ++i)
p2 = p2->next;
// Find entrance point to loop
while(p1->next != p2->next)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
On Aug 31, 8:18 am, ravi maggon <[email protected]> wrote:
> In one of my interview at winshuttle I was asked the same ques but their was
> an addon to this. Find the point where the loop occurs.
> For eg:
> 1->2->3->4->5->6->7->8->9->5
>
> so output should be 5
>
> can anyone give the algo for this.
>
> On Wed, Aug 31, 2011 at 6:44 PM, Piyush Grover
> <[email protected]>wrote:
>
>
>
> > This is fine but adding a twist to it.
> > Find number of nodes which are not in the loop.
>
> > On Wed, Aug 31, 2011 at 6:27 PM, rahul sharma
> > <[email protected]>wrote:
>
> >> int loop(void *head1,void *head2)
> >> {
> >> //head1 and head2 initialized to start;
> >> while(head1!=NULL && head2!=NULL)
> >> {
> >> head1=head1->next;
> >> head2=head2->next->next;
> >> if(head1==head2)
> >> return 1;////tehre is loop;
> >> }
> >> return 0;//no loop
> >> }
>
> >> hi guys is it corect for finding the loop...if any test case that wont
> >> works here plz tell...
>
> >> --
> >> 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.
>
> --
>
> Regards
> Ravi Maggon
> Final Year, B.E. CSE
> Thapar University
--
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.
