:-S
On 4/4/07, Dhruva Sagar <[EMAIL PROTECTED]> wrote:
>
> 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 loopingNode;
> > }
> >
> > 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.
--
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 [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
-~----------~----~----~----~------~----~------~--~---
