## C++ program to delete the middle node in a linked list:

Deleting the middle node requires the length. If we know the length, finding out the middle node is easy. For an *even* list, *(length/2 + 1)* is the middle node and for an *odd* list, *(length + 1)/2* is the middle node position.
For a *linked list*, we can have an *infinite* number of *nodes* and finding the length requires traversing the list. But there is a way that can be used to find the mid node in a linked list. In this post, I will show you how to find the *middle node* and how to delete it in a linked list.

### Finding the middle node in a linked list:

As I mentioned above, finding out the middle node is the tricky part. For that we will use the following steps :

- Create two
*node pointers*both pointed to*head*at start. - Move one pointer by
*one step*and move another by*two steps*. - Repeat
*step 2*until the faster pointer reaches the end of the linked list. - If the
*fast*pointer reaches the end, the another pointer will reach the middle. We can delete this middle node.

Let’s check the *C++* program to write these steps:

### C++ program to delete the middle node in a linked list:

Below is the complete C++ program:

```
#include <iostream>
using namespace std;
struct Node
{
int value;
Node *next;
};
class LinkedList
{
Node *head = NULL;
public:
void insertAtHead(int value)
{
Node *node = new Node;
node->value = value;
if (head == NULL)
{
node->next = NULL;
}
else
{
node->next = head;
}
head = node;
}
void deleteMiddle()
{
if (head->next == NULL)
{
head = NULL;
return;
}
Node *slowPointer = head;
Node *fastPointer = head->next;
while (fastPointer && fastPointer->next && fastPointer->next->next)
{
slowPointer = slowPointer->next;
fastPointer = fastPointer->next->next;
}
slowPointer->next = slowPointer->next->next;
}
void displayList()
{
Node *flag = head;
cout << "head"
<< "->";
while (flag != NULL)
{
cout << flag->value << "->";
flag = flag->next;
}
cout << "NULL" << endl;
}
};
int main()
{
int total, value;
LinkedList linkedList;
cout << "Enter the total nodes :" << endl;
cin >> total;
for (int i = 0; i < total; i++)
{
cout << "Enter value for node " << i << " :" << endl;
cin >> value;
linkedList.insertAtHead(value);
}
cout << "Printing the linked list :" << endl;
linkedList.displayList();
linkedList.deleteMiddle();
cout << "After middle node is deleted :"<<endl;
linkedList.displayList();
return 0;
}
```

### Explanation:

*Node*structure is used to define a node of the linked list. It can hold one integer value and pointer to the next node.*LinkedList*class is to handle all linked list operations. This class has three*public*methods.*displayList*to display the full list,*insertAtHead*to insert one node at head,and*deleteMiddle*to delete the middle node.*head*is the head pointer that points to the head node.- In the
*deleteMiddle*method, we are defining two pointers at first :*slowPointer*and*fastPointer*. At start,*slowPointer*is pointing to the first node and*fastPointer*pointing to the second node. - Using a
*while loop*, we are iterating through the linked list. On each step,*slowPointer*is moving one node and*fastPointer*is moving two nodes. - Once the
*while loop*ends, then we are removing the mid node by pointing its previous node to its next node.

### Sample output:

If you execute the above program, it will give output as like below:

```
Enter the total nodes :
5
Enter value for node 0 :
1
Enter value for node 1 :
2
Enter value for node 2 :
3
Enter value for node 3 :
4
Enter value for node 4 :
5
Printing the linked list :
head->5->4->3->2->1->NULL
After middle node is deleted :
head->5->4->2->1->NULL
Enter the total nodes :
4
Enter value for node 0 :
1
Enter value for node 1 :
2
Enter value for node 2 :
3
Enter value for node 3 :
4
Printing the linked list :
head->4->3->2->1->NULL
After middle node is deleted :
head->4->3->1->NULL
Enter the total nodes :
1
Enter value for node 0 :
10
Printing the linked list :
head->10->NULL
After middle node is deleted :
head->NULL
```