In this problem we are given a pointer to the node of a linked list, we have to write an algorithm to delete that node from the linked list.
An important thing to note here is that the pointer is pointing to that particular node, that needs to be deleted and this node can’t be the first and last node. If we are given a pointer to the last node then this problem can’t be solved.
Ex: 1 –>3 –>5 –>7 –>9 –>11 –>13 –>15 –>NULL
Now, we are given a pointer to node 5 and we have to delete it.
We can do this by replacing the integer value of the current node by the value stored in the next node until we reached the second last node and updated it’s value with the value stored in the last node and then delete the last node.
Step 1: Replace the integer value of the current node by the value stored in the next node & repeat this until we reached the second last node (x represents the old value & (x) represent the new updated value).
1 -->3 -->5(7) -->7(9) -->9(11) -->11(13) -->13(15) -->15 -->NULL
Step 2: Delete the last node.
1 -->3 -->7 -->9 -->11 -->13 -->15 -->NULL
Algorithm
Delete_Node(Node *current){
Node *temp;
if(current == NULL || current->next == NULL)
return "Can't delete the node";
while(current->next != NULL){
current->value = current->next->value;
temp = current;
current = current->next;
}
temp->next = NULL;
free(current);
return "deletion is successful";
}
Implementation of the above problem in CPP
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
int value;
Node *next;
};
string Delete_Node(Node *current){
Node *temp;
if(current == NULL || current->next == NULL)
return "Can't delete the node\n";
while(current->next != NULL){
current->value = current->next->value;
temp = current;
current = current->next;
}
temp->next = NULL;
free(current);
return "deletion is successful\n";
}
int main(){
Node *head,*current;
current = new Node;
current->value = 1;
current->next = NULL;
head = current;
for(int i=3;i<=15;i=i+2){
Node *temp = new Node;
temp->value = i;
temp->next = NULL;
current->next = temp;
current = current->next;
}
current = head;
while(current!=NULL){
cout<<current->value<<" ";
current = current->next;
}
cout<<endl;
cout<<Delete_Node(head->next->next);
current = head;
while(current!=NULL){
cout<<current->value<<" ";
current = current->next;
}
cout<<endl;
return 0;
}
Output
1 3 5 7 9 11 13 15
deletion is successful
1 3 7 9 11 13 15
Time Complexity of the above algorithm is O(N), where N is the number of nodes in the linked list.