krishnakumar_hbti

• Nov 12th, 2007

 

To get the cycle in linked list efficiently we must have to argument the data structure by having the mark information in each node and keeping head node.

mark info of head :-will keep the values indicating the value that a each unvisited node will contain for a single traversing.( this value will toggle for alternate traversals.)

mark info of other node:- will contain the information that node is visited or not. to get cycle:- we will start with head node get the value of mark info and store in a temporary variable.
This value is the value that a node must contain if it is not visited in this traversal of list. then we toggle the mark value of head (in next traversal this value will be the test for un travesed nodes).

now we will visit rest node and check if this value is same as that of temporary variable. if (yes) then this is node that is not visited we will toggle mark info of node and visit next node. if (no) this node is already visited so there is cycle.

yossale

 Profile Answers by yossale 

• Jan 14th, 2008

 

The trick is NOT to change the list (meaning you can't change the data).
The solution is this:
Hold 2 pointers , and each cycle pointer A will go "jump" 2 nodes , and pointer B will "jump" 1 node. If they ever meet , there's a circle.
But how will you know if there isn't a circle? if there is no circle , one of the pointers will end up at the end of the list...

santhigkinterview

 Profile Answers by santhigkinterview 

• Jan 16th, 2008

 

Take 2 pointer. increment 1 pointer once and another pointer twice.
   keep incrementing unless pointer2 is NULL or when pointer 1 and pointer 2 are equal.

      When both pointer equal there is a Loop existing.
   otherwise no Loop Detected.

/* Source Code */
/* Assume that there is a linked list which is already existing */

void findLoop()
{
 struct llist *ptr1,*ptr2;

 ptr1 = head;
 ptr2 = head->link;

 if(ptr1 == ptr2)
  printf("nLoop Detectedn");
 else
 {
  while((ptr2 != NULL) && (ptr1 != ptr2))
  {
   ptr1 = ptr1->link;
   ptr2 = ptr2->link;
   if(ptr2 != NULL)
    ptr2 = ptr2->link;
  }
  if(ptr2 == NULL)
   printf("Loop is not Detectedn");
  else
  {
   if(ptr1 == ptr2)
   {
    printf("Loop Detectedn");
   }
  }
 }

}

j2r_jadeja

 Profile Answers by j2r_jadeja 

• Dec 25th, 2009

 

temp = link->next;
boolean b;
while(1)
{
       if(link->next == temp)
             b=true;
       if(link->next == null)
             b=false;
link=link->next;
}
if(b)
         circular
else
        not circular