Delete all even nodes of a Circular Linked List

Today we will discuss how to Delete all even nodes of a Circular Linked List. But if you are unfamiliar with the concepts of circular linked list then please refer to this link. Suppose we have a circular linked list like 1->2->3->4 and 4 points back to 1, then after deleting even numbered nodes the list should look like 1->3 and 3 pointing to 1. Here we have deleted the 2nd and 4th node. Now, let's discuss the procedure:

Procedure

1. First we will make a circular linked list. (data structures types)

2. Now a circular linked list can have even nodes or odd nodes in total.

3. So, we will divide our problem into 2 cases:

• When the circular linked list has even number of nodes.
• When the circular linked list has odd number of nodes.

4. When the list will have even number of nodes then we will delete even numbered node but in this case the last node will also be deleted so the second last node shall point to the first node now.

5. When the list will have odd number of nodes then the last node will also be odd numbered so no need to delete that node.

6. Now to know how to delete nodes go to the Explanation of code.

Code

#include<iostream> using namespace std; struct node { int data; struct node* next; }; struct node* head=NULL; class linked { public: void insert(int x) { struct node* temp=new node(); temp->data=x; temp->next=NULL; if(head==NULL) { head=temp; } else { struct node* temp1=head; while(temp1->next!=NULL) { temp1=temp1->next; } temp1->next=temp; } } void assignhead() { struct node* temp=head; while(temp->next!=NULL) { temp=temp->next; } temp->next=head; } void delete_even() { struct node* temp=head; int c=1; while(temp->next!=head) { c++; temp=temp->next; } temp=head; temp=temp->next; if(c%2==0) { struct node* temp1=head; int n=-1; while(temp->next!=head) { if(n==-1) { temp1->next=temp->next; temp1=temp1->next; } temp=temp->next; n=n*(-1); } temp1->next=head; } else if(c%2!=0) { struct node* temp1=head; int n=-1; while(temp->next!=head) { if(n==-1) { temp1->next=temp->next; temp1=temp1->next; } temp=temp->next; n=n*(-1); } } cout<<"List after deleting even-numbered nodes: "; disp(); } void disp() { struct node* temp=head; cout<<temp->data<<" "; temp=temp->next; while(temp!=head) { cout<<temp->data<<" "; temp=temp->next; } cout<<endl; } }; int main() { linked l; l.insert(3); l.insert(5); l.insert(8); l.insert(1); l.insert(9); l.insert(0); l.insert(2); l.insert(5); l.assignhead(); cout<<"original list: "; l.disp(); l.delete_even(); return 0; }

Explanation of code

1. First we will write a simple code of circular linked list which will have 3 functions:

     - insert() - which will insert elements in the circular linked list.
     - assignhead() - to make a link between last and first node.
     - disp() - which will display the circular linked list.

2. Insert some values in the circular linked list.

3. Now we have created a function named delete_even() to Delete all even nodes of a Circular Linked List.
4. First we have created a temp variable pointing to the head. Then we have created a int variable 'c' which is initialized to 1. This 'c' will be used to store the number of nodes in the circular linked list.
    struct node* temp=head;
    int c=1;
5. Then we have written a while loop which iterate the whole list and increment c in each iteration. This will give us the number of nodes present in our list. (data structures types)

   while(temp->next!=head)
   {
        c++;
        temp=temp->next;
   }
6. Now we have assigned temp to head again. And after that we have made temp point to the second node.
   temp=head;
   temp=temp->next;
7. Now we have an if condition which will be executed if we have even number of nodes (i.e c%2==0).
    if(c%2==0)
   {
          ---
   }
8. Inside the if condition we have made another pointer to node variable temp1 which is initialized to head. Then we have declared 'n' which is initialized to -1.
    struct node* temp1=head;
    int n=-1;
9. Then we have started a while loop which will iterate our circular linked list till be reach the last node.
    while(temp->next!=head)
   {
          ---
  }
10. Then we have used another if condition which checks if 'n' is equal to -1 or not. Basic idea of using 'n' is that 'n' will be -1 whenever our temp will point to an even numbered node. Since temp is initially pointing to the second node (refer to point 6) which is an even numbered node so this if condition will hold true and we will enter this if condition block. temp1 is pointing to the first node thus we have made temp1 to point to the next node of temp and then we have incremented temp1. So, temp1 will now be at 3rd node.
    if(n==-1)
    {
       temp1->next=temp->next;
       temp1=temp1->next;
    } 
11. Then we have incremented temp to next node (i.e it will also point to the 3rd node) and n will now become 1.
    temp=temp->next; 
    n=n*(-1);
12. Now if you iterate again this while loop again then you will notice that n is not -1 now so we won't enter the if block and we actually didn't wanted to enter the if block because we are at an odd numbered node (3rd node). I hope you can make sense of it now.
13. After this while loop gets over the we have written made temp1 to point to the first node because in this case we had even number of nodes so after deleting all even number of nodes the last node will also be even so we will delete that too. But then the second last node shall point to the first node. In this case that second last node will be temp1. (data structures types)

    temp1->next=head;
14. Next we have written another if condition which is for odd number of nodes. The complete logic will be same for odd number of nodes. Just one change will be there that the last node in this case will not be deleted because we have odd number of nodes so no need to write temp1->next=head;


Guys you can follow me here :

https://github.com/mayank171

https://www.linkedin.com/in/mayank-mewar-586090173/