Q:

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

mahmoud2506
Save to bookmark
|
2022-05-07
|
  278 
0

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

 

C++ programming, exam questions, C++ programming exam-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-07
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Data Structure programs using C and C++ (Linked List Programs)
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Delete keys in a Linked list using C++ program... >>
<< C program to display a Linked List in Reverse...