This is the right one, with the correction. temp1 -> temp.
By the way aakash, that point was a good one.
On 4/4/07, Dhruva Sagar <[EMAIL PROTECTED]> wrote:
>
> 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=temp->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.
--
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
-~----------~----~----~----~------~----~------~--~---
