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

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

#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);
    }
}

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.

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.

Previous post Print the reverse of a linked list without extra space and modifications
Next post C Program For Merge Sort For Linked Lists

Leave a Reply

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