Based on aakash's explanation there is another solution (similar to point no
2.)
Traverse the link list and keep nulling the pointers in the link list. When
you reach the end, the last node you reach to is the node where the looping
is occurring.
Node*findLoopingNode(Node*start) {
Node*temp=start,*loopingNode=start;
while(loopingNode->next) {
loopingNode=temp1->next;
temp->next=null;
temp=loopingNode;
}
return temp2;
}
I have made some more changes below with red.
On 4/4/07, aakash mandhar <[EMAIL PROTECTED]> wrote:
>
> There are many efficient ways to do this. I am listing them out.
>
> 1) Use two pointers. One advancing one node at a time and the other
> advancing 2 nodes at a time. So that the relative speed between them is
> always one node. If the first and second pointer coincide then there is a
> loop.
>
> 2) Destructive method. While travesing make each pointer point to itself.
> When you reach a node which points to itself there is a loop.
>
> 3) Reverse the linked list as you traverse. If you reach the starting node
> again. then there is a loop.
>
> 4) Similar to first. But here move the first node by one and keep moving
> the other node in multiples of two. During the movement compare if the two
> nodes meet. If not advance the first node to the second node and start
> moving again.
>
> Regards,
> Aakash
>
> On 4/4/07, Dhruva Sagar <[EMAIL PROTECTED]> wrote:
> >
> > An alternate solution may be something like this:
> >
> > You have two loops. one inside another.
> >
> Node*findLoopingNode(Node*Start) {
> >
> node*temp1=start,*temp2=start;
> > node*loopingNode=null;
> > while(temp1) {
> > while(temp2) {
> > if(temp1->next=temp2->next) {
> > loopingNode=temp1->next;
> > break;
> > }
> > temp2=temp2->next;
> > }
> > if(loopingNode!=null)
> > break;
> > temp1=temp1->next;
> > }
>
> return loopingNode;
> >
> }
>
> On 4/4/07, Pradeep Juneja <[EMAIL PROTECTED]> wrote:
> > >
> > >
> > >
> > > How can we know at what node, list has the loop ?
> > > i.e
> > > A---->B----->*C*------->D------>E------F-----
> > > |
> > > |
> > > ----------------------------- - -|
> > >
> > >
> > >
> >
> >
> > --
> > Thanks & Regards,
> > Dhruva Sagar.
> >
> >
> >
>
> >
>
--
Thanks & Regards,
Dhruva Sagar.
--~--~---------~--~----~------------~-------~--~----~
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 email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
