@ ravi
take 2 pointer
one initialize by head another by the point where 2 pointer meets (as
in first post of rahul sharma)
increment the second pointer by one till it reach to the same node or
the first node
if it reach the node pointed by first then this one is point of cycle
otherwise increment the first node by one and continue.
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)
print ("loop detected");////tehre is loop;
find_loop(head1)
}
return 0;//no loop
}
void find_loop(head1)
{
p1=head // head of the original link list
p2=head1;
p2=p2->next;
if(p2!=head1 && p2!=p1)
{
p2=p2->next;
}
printf("point of circle %d" p1->data);
p1=p1->next;
}
On Aug 31, 7:49 pm, Don <[email protected]> wrote:
> @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.
