Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp on Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given a pointer to a node to be deleted in a singly linked list. We have to delete that node from the list.

Problem Statement Understanding

Well, our lives would’ve been easier if we were given the pointer to the head.

  • In that case, a simple traversal would’ve done the job.

But, here, we don’t have a pointer to the head; instead we have a pointer to the node that is to be deleted.

Suppose the given list is

and we have a pointer to 2.

  • So, according to the problem statement, we have to delete 2 from the list, and also we don’t have the head pointer.
  • The final resultant list will be after deletion of 2 will be

Well, now that we’ve understood the problem statement, let us discuss how we can approach this problem.

So, how should we approach this problem?

  • Well, instead of deleting the node, we can copy the data from the next node and then delete the next node. This will work. Let us dive deeper into the approach section.

Approach

Our approach is going to be pretty straightforward.

  • Suppose the pointer given is node (Pointer node is pointing to the node to be deleted).

  • Now, to delete the node to which pointer node is pointing, we will perform the following steps:

    • First, we will copy the data of node → next in node.
    • Then, we will create a pointer, say temp, and point it to node -> next.
    • After that, we will make node -> next point to node -> next -> next.
    • In the end, we will delete temp.
  • Finally, after performing the above steps, our task will be over, the node to which pointer node was pointing will get deleted from the list.

Let us take an example.

  • Suppose our list is 1 → 2 → 3 → 4, and we have a pointer to the node with value 2.
  • According to the problem statement, we have to delete 2.
  • Now, instead of deleting 2, we will first copy the value of 2 → next, i.e., 3 in 2.
  • So, after copying, the list will look like 1 → 3 → 3 → 4.
  • Now, we will simply make the 2nd node point to 4.
  • So, our final list will be 1 → 3 → 4.
  • As we can see, we have successfully deleted the node with value 2 from the list.

Note: This approach will only work if the node to be deleted is not the last node of the list. As we are copying the next node's data, the last node doesn't have a next node, so it would throw an error.

Algorithm

  • Create a pointer temp and store current node’s next in it.
  • Now, copy the current node’s next’s data in the current node using current - > data = temp - > data (As temp = current - > next)
  • Now, as the data has been copied, we can delete the next node of the current. So, make current - > next = temp - > next (Changing links).
  • In the end, free(temp).

Dry Run

Code Implementation

#include 
#include 
using namespace std;

/* Structure of a linked list node */
class Node {
public:
    int data;
    Node* next;
};

/* Inserting a node at the head of a linked list */
void push(Node** head_ref, int new_data)
{

    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

/* Using this function we will be printing the content of the linked list */
void printList(Node* head)
{
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

/* Using this function we will be deleting a node whose pointer is given in input */
void deleteNode(Node* node_ptr)
{
    if (node_ptr->next == NULL)
    {
        free(node_ptr);
    
        return;
    }
    
    Node* temp = node_ptr->next;
    node_ptr->data = temp->data;
    node_ptr->next = temp->next;
    free(temp);
}

/* Main function (driver function) */
int main()
{
    Node* head = NULL;

    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);

    cout << "Linked list before deleting the node \n";
    printList(head);

    deleteNode(head->next);

    cout << "\nLinked list after deleting the node \n";
    printList(head);
    return 0;
}
public class LinkedList {

    static Node head;
    /* Node structure of a linked list */
    static class Node {

        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
    
    /* Using this function we will be printing the content of the linked list */
    void printList(Node node)
    {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }

    /* Using this function we will be deleting a node whose pointer is given in input */
    void deleteNode(Node node)
    {
        Node temp = node.next;
        node.data = temp.data;
        node.next = temp.next;
        System.gc();
    }
    
    /* Main function (Driver function) */
    public static void main(String[] args)
    {
        LinkedList list = new LinkedList();
        list.head = new Node(1);
        list.head.next = new Node(2);
        list.head.next.next = new Node(3);
        list.head.next.next.next = new Node(4);

        System.out.println("Linked list before deleting the node");
        list.printList(head);

        list.deleteNode(head.next);
        System.out.println("");
        System.out.println("Linked list after deleting the node ");
        list.printList(head);
    }
}
#include 
#include 
#include 
 
/* Link list node */
struct Node {
    int data;
    struct Node* next;
};
 
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
 
    /* put in the data  */
    new_node->data = new_data;
 
    /* link the old list off the new node */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
void printList(struct Node* head)
{
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d  ", temp->data);
        temp = temp->next;
    }
}
 
void deleteNode(struct Node* node_ptr)
{
    if (node_ptr->next == NULL)
    {
        free(node_ptr);
        
        return;
    }
    struct Node* temp = node_ptr->next;
    node_ptr->data = temp->data;
    node_ptr->next = temp->next;
    free(temp);
}
 
int main()
{
    struct Node* head = NULL;
 
    /* Use push() to construct below list
    1->12->1->4->1  */
    push(&head, 1);
    push(&head, 4);
    push(&head, 1);
    push(&head, 12);
    push(&head, 1);
 
    printf("\n Before deleting \n");
    printList(head);
 
    deleteNode(head);
 
    printf("\n After deleting \n");
    printList(head);
    getchar();
}
class Node():
	def __init__(self):
		self.data = None
		self.next = None

def push(head_ref, new_data):

	new_node = Node()
	new_node.data = new_data
	new_node.next = head_ref
	head_ref = new_node

	return head_ref


def printList(head):
	temp = head
	while(temp != None):
		print(temp.data, end=' ')
		temp = temp.next


def deleteNode(node_ptr):
	temp = node_ptr.next
	node_ptr.data = temp.data
	node_ptr.next = temp.next


if __name__ == '__main__':

	head = None

	head = push(head, 4)
	head = push(head, 3)
	head = push(head, 2)
	head = push(head, 1)

	print("Before deleting ")
	printList(head)

	deleteNode(head.next)

	print("\nAfter deleting")
	printList(head)

Output

Linked list before deleting the node
1 2 3 4
Linked list after deleting the node
1 3 4

Time Complexity: O(1), as no traversal is needed.

[forminator_quiz id="5359"]

So, in this article, we have tried to explain how to delete a node from a linked list, if only a pointer to that node is given. This is a very tricky and important question when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Leave a Reply

Your email address will not be published. Required fields are marked *