Delete A Node In A Linked list When The Pointer To The Head Node Is Not Given

Let's start by understanding the problem statement for this task.

You are given the pointer to the node to be deleted, and you have to delete the node without traversing the linked list through the head node pointer.

Hint:

For deleting a given node without actually traversing the linked list from the head node can be achieved when, we copy the data of the node next to the node to be deleted into a temporary node and delete the next node, for this we actually don’t need to traverse through the whole of the linked list.

Quick Think:

For deleting the node whose only pointer is given, we have to ponder over the following points:-

• We have to delete the node without traversing the linked list, as we are given only the reference to the node to be deleted.
• We have to copy the data of the node next to the node to be deleted, and we will delete the next node, as we have only the link to the node to be deleted.

Algorithm:

For solving the above problem, we have to create a function with arguments as the reference to the node to be deleted and function to push the node and the function to print the data of the node and follow the steps below to reach the final output:-

Step1: For deleting the node whose reference is given, we have to define a temporary node.

Step2: Copy the data of the node next to the node to be deleted.

Step3: Now, point the link of the node to be deleted to the next to next node, as the next node is the only node to be deleted.

Step4: Now, delete the node and hence, the node whose pointer is given is deleted and we obtain our result.

Implementation Of The Above Algorithm:

Now let's see the implementation of the above algorithm,

#include <bits/stdc++.h>
using namespace std;
struct node
{
	int data;
	struct node * next;
};

/*Function to push the node in the linked list. */
void push(struct node **head_ref, int data)
{
	struct node * node;
	node = (struct node *) malloc(sizeof(struct node));
	node->data = data;
	node->next = (*head_ref);
	(*head_ref) = node;
}

/*Function to delete the node. */
void deletenode(struct node *delete_node)
{
	/*Define the temprary node. */
	struct node * temp;
	/*Store the reference of the current node to the next node of the list. */
	temp = delete_node->next;
	/*Store the data of the node next to the node to be deleted. */
	delete_node->data = temp->data;
	/*Link the node to the next of the node to be deleted. */
	delete_node->next = temp->next;
	/*Delete the node. */
	free(temp);
}

/*Function to print the linked list. */
void printlist(struct node *head)
{
	while (head != NULL)
	{
		cout << head->data << " ";
		head = head->next;
	}
}

/*Driver function to test the above algorithm. */
int main()
{
	struct node *head = NULL;
	push(&head, 1);
	push(&head, 6);
	push(&head, 7);
	push(&head, 3);
	push(&head, 2);
	cout << "Node before deletion" << endl;
	printlist(head);
	cout << endl;
	cout << "Node after deletion" << endl;
	deletenode(head->next->next);
	printlist(head);
	return 0;
}

The time complexity of the above diagram: O(1).

The output of the above algorithm 2 3 6 1.

Explanation Of The Above Algorithm:

Let us consider the linked list given in the diagram above and suppose we have to delete the node with data 7, so we will proceed in the following manner:-

• Define a temporary node and point it to the node next to the node to be deleted.

• Copy the data of the node next to the node to be deleted in the node whose pointer is known, here in this case of the node with data 6 as shown in the above diagram.

• Now, point the next of the node to be deleted to the next of the temporary node, as shown in the above diagram.
• And, delete the node.