w3resource

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>

using namespace std;

struct Node
{   
    int num;
    Node *next;
 }; //node constructed

  int size = 0;
  void insert(Node** head, int num){
    Node* new_Node = new Node();
    new_Node->num = num;
    new_Node->next = *head;
    *head = new_Node;    
     size++;
}

Node* get_Middle(Node* head) {
    
    // Base cases 
    if (head == NULL) 
        return NULL; 
    if (head->next == NULL) 
    { 
        delete head; 
        return NULL; 
    } 
      // Set up slow and fast pointers in order 
	  // to reach the middle of the linked list 
    Node* slow_ptr = head; 
    Node* fast_ptr = head; 
  
    // Find the middle and previous of middle. 
    Node* prev; // To store previous of slow_ptr 
    while (fast_ptr != NULL && fast_ptr->next != NULL) 
    { 
        fast_ptr = fast_ptr->next->next; 
        prev = slow_ptr; 
        slow_ptr = slow_ptr->next; 
    } 
     //Delete the middle node 
    prev->next = slow_ptr->next; 
    delete slow_ptr; 
    return head;
    
}

  //Display all nodes
  void display_all_nodes(Node* node)
    { 
      while(node!=NULL){
        cout << node->num << " "; 
        node = node->next; 
    } 
}

int main()
{
    Node* head = NULL;

    insert(&head,1);
    insert(&head,3);
    insert(&head,5);
    insert(&head,7);
    insert(&head,9);
    cout << "Original list:\n";
    display_all_nodes(head); 
    cout << "\nAfter removing the middle element of the said list:\n";
    Node* 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 << "\nAfter removing the middle element of the said list:\n";
    result = get_Middle(head);
    display_all_nodes(result); 
    cout<<endl;
    return 0;
}

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:

Flowchart: Delete a middle node from a Singly Linked List.
Flowchart: Delete a middle node from a Singly Linked List.

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.

What is the difficulty level of this exercise?



Share this Tutorial / Exercise on : Facebook and Twitter

C++ Programming: Tips of the Day

How to replace all occurrences of a character in string?

std::string doesn't contain such function but you could use stand-alone replace function from algorithm header.

#include <algorithm>
#include <string>

void some_func() {
  std::string s = "example string";
  std::replace( s.begin(), s.end(), 'x', 'y'); // replace all 'x' to 'y'
}

Ref: https://bit.ly/3niU71x