Home Practice Programming Given a pointer to the node of a linked list delete that...

Given a pointer to the node of a linked list delete that node

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.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promsie, we won't spam
Even we hate spam as much as you hate them

Books recommendation for interview preparation