C++ Linked List Exercises: Delete a middle node from a Singly Linked List

C++ Linked List: Exercise-11 with Solution

Write a C++ program to delete a node from the middle of Singly Linked List.

Test Data:
Original list:
9 7 5 3 1
After removing the middle element of the said list:
9 7 3 1
After removing the middle element of the said list:
9 7 1
After removing the middle element of the said list:
9 1
After removing the middle element of the said list:
9

Sample Solution:

C++ Code:

#include <iostream> // Including input-output stream header file

using namespace std; // Using standard namespace

struct Node // Declare a structure for defining a Node
{   
    int num; // Data field to store a number
    Node *next; // Pointer to the next node
}; // Node constructed

int sizen = 0; // Initializing variable to keep track of the size of the linked list

// Function to insert a node at the start of the linked list
void insert(Node** head, int num){
    Node* new_Node = new Node(); // Creating a new node
    new_Node->num = num; // Assigning data to the new node
    new_Node->next = *head; // Pointing the new node to the current head
    *head = new_Node; // Making the new node as the head
    sizen++; // Increasing the size of the linked list
}

// Function to remove the middle node of the linked list
Node* get_Middle(Node* head) {
    if (head == NULL) // Base case: if the list is empty
        return NULL; 

    if (head->next == NULL) { // Base case: if there's only one node in the list
        delete head; // Delete the head node
        return NULL; 
    }

    Node* slow_ptr = head; // Pointer for slow traversal
    Node* fast_ptr = head; // Pointer for fast traversal

    Node* prev; // To store previous of slow_ptr 
    while (fast_ptr != NULL && fast_ptr->next != NULL) { // Loop to reach the middle of the linked list
        fast_ptr = fast_ptr->next->next; 
        prev = slow_ptr; 
        slow_ptr = slow_ptr->next; 
    } 

    prev->next = slow_ptr->next; // Delete the middle node
    delete slow_ptr; // Free memory allocated for the middle node
    return head; // Return the updated head
}

// Function to display all nodes in the linked list
void display_all_nodes(Node* node) {
    while (node != NULL) { // Loop through all nodes until the end is reached
        cout << node->num << " "; // Displaying the data in the current node
        node = node->next; // Move to the next node
    } 
}

int main() {
    Node* head = NULL; // Initializing the head of the linked list as NULL

    insert(&head,1); // Inserting a node with value 1
    insert(&head,3); // Inserting a node with value 3
    insert(&head,5); // Inserting a node with value 5
    insert(&head,7); // Inserting a node with value 7
    insert(&head,9); // Inserting a node with value 9

    cout << "Original list:\n"; // Displaying message for the original list
    display_all_nodes(head); // Displaying all nodes in the original list

    cout << "\nAfter removing the middle element of the said list:\n"; // Displaying message for removal of middle element
    Node* result = get_Middle(head); // Removing the middle element of the list
    display_all_nodes(result); // Displaying all nodes after removal

    cout << "\nAfter removing the middle element of the said list:\n";
    result = get_Middle(head);
    display_all_nodes(result); 

    cout << "\nAfter removing the middle element of the said list:\n";
    result = get_Middle(head);
    display_all_nodes(result); 

    cout << "\nAfter removing the middle element of the said list:\n";
    result = get_Middle(head);
    display_all_nodes(result); 

    cout << endl; // Displaying newline
    return 0; // Returning from the main function
}

Sample Output:

Original list:
9 7 5 3 1
After removing the middle element of the said list:
9 7 3 1
After removing the middle element of the said list:
9 7 1
After removing the middle element of the said list:
9 1
After removing the middle element of the said list:
9

Flowchart:

CPP Code Editor:

Contribute your code and comments through Disqus.

Previous C++ Exercise: Delete first node of a Singly Linked List.
Next C++ Exercise: Delete the last node of a Singly Linked List.