ALGO: Does the circular linked list and loop in the linked list have same meaning or different ?

Question

What is the best logic or way to detected linked list has loop ?
And also what is the best way to find out that given linked list is circular ?

Answer 1

Both are same as last node of the circular link list has address of very first node of link list ,also it signifies the loop in link list.
Traverse through the last node of link list than check if(last_node->next==start) if yes than list is circular otherwise not

Comments

Shashi,I think both have subset like relationship example: if last node of list has address of first node then it is circular but in case of loop,it is not necessary that last node has the address of first node,it may have first node ,second node third node... etc except own address.so Circular linked list is subset of loop in the linked list.

---

i think you are right...thanks

Answer 2

You can detect a loop in a linked list by using below logic:

int find_loop(node *head){
   node *next=head;
   node *temp;
   for( temp=head;temp!=NULL;temp=temp->ptr){
         temp=temp->ptr;

         if(temp->ptr!=NULL)
             temp=temp->ptr;

         next=next->ptr;

         if(temp==next)
            printf("Loop");

         return 0;
     }
     printf("No Loop")
     return 0;    
}

To find a circle:

int find_circle(node *head){
   node *temp;
   for( temp=head;temp!=NULL;temp=temp->ptr){
         temp=temp->ptr;
         if(temp==head)
           printf("Circle")
         return 0;
     }
     printf("No Circle")
     return 0;    
}