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*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;
> }
>
> 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.
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
