Delete middle element of a linked list

Today we will discuss how to delete middle element of a linked list. But before moving to the solution you should be familiar with the concept of linked list.

 Procedure

First we will make a linked list.
Then we will count the number of nodes in a linked list.
Now we will have 2 cases -
1.) when the number of nodes are even then we will have 2 middle elements (n/2 and n/2+1).
2.) when the number of nodes are odd then we will have 1 middle element ((n+1)/2).
Then we will write the underlying code to delete middle element by analyzing if the number of nodes are even or odd.

Algorithm

We will first write a simple code which will have 2 functions:

1. insert() - which will insert elements to linked list.
2. show() - to display the linked list.

Now we will make a function deletemiddle() which will delete the middle element.
In the deletemiddle() we will make 1 node temp1 which will initially point to head of the linked list.
Then we will count the number of nodes in the linked list by traversing the list with temp1 and storing the count values in a count variable.
Now again we will initialize temp1 to head.
Now we will check count%2 == 0 (even) or count%2!=0 (odd).

If count%2==0 or number of nodes are even then:
1. We will find mid by count/2.
2. We will make a variable p of int type which will tell us if we have reached the desired node or not.
3. Now we will traverse the list. We will increment p with each iteration and also check if p+1 == mid or not.
4. If p+1 == mid that means the next node is then first middle node and the next node is the second middle node.
5. So we will use (temp1->next=temp1->next->next->next) which means to put the address of the node after the second middle element in the current node.

If count%2!=0 or number of nodes are odd then:
1. We will find mid by count/2.
2. We will make a variable p of int type which will tell us if we have reached the desired node or not.
3. Now we will traverse the list. We will increment p with each iteration and also check if p+1 == mid or not.
4. If p+1 == mid that means the next node is then middle node .
5. 5. So we will use (temp1->next=temp1->next->next) which means to put the address of the node after the middle element in the current node.

Implementation in C++

#include<iostream> using namespace std; struct node { int data; struct node* next; }; struct node* head=NULL ; void insert(int x) //function it insert elements { 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; temp->next=NULL; } } void deletemiddle() //function to delete middle element { struct node *temp1=head; int count=0; while(temp1!=NULL) //count number of nodes in linked list { count++; temp1=temp1->next; } temp1=head; if(count%2==0) //if number of nodes are even { int mid1=count/2; //find mid of linked list int p=0; //it will tell if we have reached mid or not while(temp1!=NULL) { p++; if(p+1==mid1) // it means next node is the mid of linked list { temp1->next=temp1->next->next->next; } temp1=temp1->next; } } else if(count%2!=0) //if number of nodes are odd { int mid=(count+1)/2; //find mid of linked list int p=0; //it will tell if we have reached mid or not while(temp1!=NULL) { p++; if(p+1==mid) // it means next node is the mid of linked list { temp1->next=temp1->next->next; } temp1=temp1->next; } } } void show() //function to display linked list { struct node* temp=head; while(temp!=NULL) { cout<<temp->data<<" "; temp=temp->next; } cout<<endl; } int main() { insert(2); insert(4); insert(-3); insert(7); insert(9); insert(8); insert(-13); cout<<"original linked list: "; show(); cout<<endl; cout<<"after deleting middle element: "; deletemiddle(); show(); return 0; }

If you have any doubts then please ask in the comment section below.