Is it circular link list?

[BigAl]

How do I know, a given link list is a circular link list?

Thanks,
Al

[Troll_King]

A linked list is a set of items where each item is part of a node that also contains a link to a node.

We most often work with lists that correspond to a simple sequential arrangement of the items, adopting one of the following conventions for the link in the final node:

• It is a null link that points to no node.
  It refers to a dummy node that contains no item.
  It refers back to the first node, making the list a circular list.

Excerpts from Sedgewick.

[The V.]

Pick any node in the list. Keep traversing the list in one direction until you either hit NULL, or you return to the node you started from. If you hit NULL, it's not a circular list, if you got back to where you began, it is.

[-KEN-]

THis might work...untested and all...

current = first;

while(current->next != first)
{

     if(current->next == NULL)
     {
           printf("normal list!\n");
           break;
     }

     else
           current = current->next;
}
     if(current->next != NULL);
          printf("circular, baby!\n");

[quzah]

Your test fails in this example:

node1 -> node2 -> node3 -> node4 ->node5 ->node3 ->

See? If your list is circular, but not a first -> last circular, then your loop fails. This is how you test for a circular list, with _the least_ resources involved:

Node *n1, *n2;

n1 = n2 = myListToTestForCircularity;
do {
   if( n2->next && n2->next->next )
   {
      n2 = n2->next->next;
      n1 = n1->next;
   }
   if( n1 == n2 ) {
      printf("Is a loop.");
   }
   else
   {
      printf("Not a loop.");
      break;
   }
} while( n1 != n2 && !loop );

See, it works like this:

Advance 1 pointer 1 time.
Advance another pointer twice.
If pointer 1 ever equals pointer 2, you have a loop.

JC Lawrence taught me that one. Props to him.

Quzah.

[-KEN-]

always tryin to show me up