Program to add a node to rear of circular linked list

 Let us write

Write a program to add a node to the rear of a circular linked list.

Now a circular linked list has no end. That is to say, the last node in the list points back to the head of the list. So finding the last node will be slightly tricky.

• let temp = head
  
• while temp->next !=head
  
• temp = temp->next

Once we find the last node, we append the new node here. But we must not forget to point his new node back to head.

• lastnode->next = newnode;
• newnode->next = head;

The complexity is O(n). 

 Here is the complete program

 #include<iostream>  
 using namespace std;  
 struct node  
 {  
   int n;  
   node *next;  
 };  
 class linked_list  
 {  
   node *head;  
  public:  
    linked_list(int val = 0)  
    {  
      if(val==0)  
     head = NULL;  
     else{  
       head = new node;  
       head->n = val;  
       head->next = NULL;  
    }  
     }  
     node* find_last_node()  
     {  
       if(head==NULL || head->next==head)  
         return head;  
       node* temp = head;  
       while(temp->next!=head){  
         temp = temp->next;  
       }   
       return temp;  
     }  
     void append(int val)  
    {  
      node *nd = new node;  
      nd->n = val;  
      nd->next = NULL;  
      node *last_node = find_last_node();  
      if(last_node!=NULL)   
      {  
     last_node->next = nd;  
     nd->next = head;  
      }  
      else if(head==NULL)/*list empty*/  
    {  
        head = nd;  
      nd->next = nd;  
      }  
   else{/*only one node*/  
     head->next = nd;  
     nd->next = head;  
      }    
    }  
    void display()  
    {  
       node* temp = head;  
       do  
       {  
         cout<<temp->n<<" ";  
         temp = temp->next;  
       }while(temp!=head);  
    }   
 };  
 int main()  
 {  
    linked_list lst;  
    for(int i = 0;i<10;i++)  
    {  
      int n;  
      cout<<"Number:";  
      cin>>n;  
      lst.append(n);  
    }   
    cout<<"The linked list is ";  
    lst.display();    
 }