Home » C++ programs » D.S. programs

Delete the middle node of a Linked List in C++

C++ deleting middle node from Linked list: Here, we are implementing C++ program to delete middle node of a linked list in C++.
Submitted by Souvik Saha, on May 04, 2019

Given a single Linked List and we have to delete the middle the element of the Linked List.

If the length of the linked list is odd then delete (( n+1)/2)th term of the linked list and if the list is of even length then delete the (n/2+1)th term of the liked list.

Example 1:

    If we have a Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7
    After deleting the middle node the linked list will be: 
    1 → 2 → 3 → 5 → 6 → 7 
    4 is the middle node

Example 2:

    If we have a Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
    After deleting the middle node the linked list will be: 
    1 → 2 → 3 → 4 → 6 → 7 → 8
    5 is the middle node

Algorithm:

To solve the problem we follow the following procedure,

1. We initiate the two node pointer name as slow, fast. (like Floyd's tortoise algo, refer the link to my article of merge sort in the linked list).
2. Each time we increment the slow by one whereas increment the fast pointer by two.
3. Repeat step 2 until the fast pointer goes to the end of the linked list.
4. When fast pointer goes to the end of the list at the same time slow pointer points to the middle of the linked list.
5. Then delete the middle node.

C++ implementation:

#include <bits/stdc++.h>
using namespace std;

struct node{
    int data;
    node* next;
};

//Create a new node
struct node* create_node(int x){
    struct node* temp= new node;
    temp->data=x;
    temp->next=NULL;
    return temp;
}

//Enter the node into the linked list
void push(node** head,int x){
    struct node* store=create_node(x);
    if(*head==NULL){
        *head =store;
        return;
    }
    struct node* temp=*head;
    while(temp->next){
        temp=temp->next;
    }
    temp->next=store;
}

//Delete the middle node from the linked list
void delete_node(node** head){
    if((*head)->next==NULL){
        *head=NULL;
        return;
    }
    struct node* fast=(*head)->next;
    struct node* slow=*head;
    while(fast && fast->next && fast->next->next){
        slow=slow->next;
        fast=fast->next->next;
    }
    slow->next=slow->next->next;
}

//Print the list
void print(node* head){
	struct node* temp=head;
	while(temp){
		cout<<temp->data<<" ";
		temp=temp->next;
	}
}

int main()
{
    struct node* l=NULL;
    push(&l,1);
    push(&l,2);
    push(&l,3);
    push(&l,4);
    push(&l,5);
    push(&l,6);
    cout<<"Before the delete operation"<<endl;
    print(l);
    delete_node(&l);
    cout<<"\nAfter the delete operation"<<endl;
    print(l);
    return 0;
}

Output

Before the delete operation
1 2 3 4 5 6
After the delete operation
1 2 3 5 6