Delete a node when only a pointer/reference to a node is given in a singly linked list

Given a pointer to a node in a singly linked list. We need to delete the node. Head of the node is not provided

Example

Given input linked list

Delete 5

Here only pointer of 5 given.

Algorithm

Time complexity : O(1)

Step 1 : create a function which takes a node pointer and deletes it.
Step 2 : copy the data from the next node to the node to be deleted.
a)    Copy the data into present node.
b)    And change next of present node.
c)    Delete the next node of present node.

Algorithm working

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct LL{
	int data;
	LL *next;	
};


void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
	struct LL* curr=new LL;
		
		curr->data=dataToBeInserted;
		curr->next=NULL;
	
	if(*head==NULL)
			*head=curr; //if this is first node make this as head of list
		
	else
		{
			curr->next=*head; //else make the current (new) node's next point to head and make this new node a the head
			*head=curr;
		}
		
		//O(1) constant time
}

void deleteNode(struct LL *&ptr) //take the reference so that whatever changes you do the ptr here it gets reflected everywhere 
{
	//According to question we do not know the head pointer 
	//The head pointer is just to build the linked list
	//Approach is first check if it is last node then simply make it NULL (dont delete orelse the previous node will point to dangling pointer).
	//Else copy data of next node of the given node and delete the next node
	
	if(ptr->next == NULL)
		ptr = NULL;
		
	else
	{
		struct LL * temp = ptr->next; //store the pointer to the next of given node
		ptr->data = ptr->next->data;  //copy the contents of the next node
		ptr->next = temp->next;  //make the next of given node to the remaining list 
		delete(temp);
	}
	
	
}

void display(struct LL**head)
{
	struct LL*temp=*head;
	while(temp!=NULL)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}


int main()
{
	
	struct LL *head = NULL; //initial list has no elements
	insertAtBeginning(&head,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);
	cout<<"Current List is :-\n";
	display(&head);
	
	//Remove 'next' to check for all locations
	deleteNode(head->next->next->next->next->next); //Last node deletion 
	cout<<"After deleting the node"<<endl;
	
	display(&head);
	
	return 0;
}
Try It


Next > < Prev
Scroll to Top