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

Delete middle node of linked list in C++: In this tutorial, we will learn how to delete the middle node of a linked list using the C++ program? By Souvik Saha Last updated : August 01, 2023

Problem statement

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

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 delete the middle node of a linked list

To solve the problem we follow the following procedure,

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).
Each time we increment the slow by one whereas increment the fast pointer by two.
Repeat step 2 until the fast pointer goes to the end of the linked list.
When fast pointer goes to the end of the list at the same time slow pointer points to the middle of the linked list.
Then delete the middle node.

C++ program to delete the middle node of a linked list

#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