Oct 242016
 

Write a function that prints all the elements of a circular linked list. (or traverse a circular linked list)

Solution

In a normal (not Circular) linked list the next pointer of last node is null as shown in the below picture.rotate linked list

So the below loop will print all the nodes of the list

while(h->next != NULL)
{
   cout<< h->data;
   h = h-> next;
}

But if the list is circular then next pointer of last node will be holding the address of first node. In fact there is no node in the list whose next pointer is NULL, so the above loop will be infinite loop.

In this case we just need two pointers, one will stay on the first node (head node) and other will traverse thru the list, when the second pointer becomes equal to the first, it means the entire list is printed and we will stop

void printCircularList(Node* h)
{
   if(h == NULL)
      return;
   Node* t = h; // this pointer will not move.

   do
   {
      cout<< h->data;
      h = h-> next;
   }while(h != t);
}

 

 

pinkdiamonds.nl

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)