Vultr DocsLatest Content

Delete Node in a Linked List

Updated on 21 May, 2025
Delete Node in a Linked List header image

Problem Statement

In the given problem, we are dealing with the manipulation of a singly-linked list. The task involves deleting a specific node from this list. Notably, this node is directly provided to us, meaning we do not start with a reference to the head of the list. It's important to highlight that all nodes have unique values and the node designated for deletion is not the last one in the list.

To "delete" the node, we modify the list such that:

  • The unique value of the given node no longer appears anywhere in the linked list.
  • The overall count of nodes is reduced by one.
  • The order of nodes before and after the target node remains unchanged.

The testing structure for this problem will consist of constructing the list from provided input and then performing the deletion operation to verify the correct restructuring of the list.

Examples

Example 1

Input:

head = [4,5,1,9], node = 5

Output:

[4,1,9]

Explanation:

You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2

Input:

head = [4,5,1,9], node = 1

Output:

[4,5,9]

Explanation:

You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Constraints

  • The number of the nodes in the given list is in the range [2, 1000].
  • -1000 <= Node.val <= 1000
  • The value of each node in the list is unique.
  • The node to be deleted is in the list and is not a tail node.

Approach and Intuition

When tasked with deleting a node from a singly-linked list without access to the head node, we are limited in our approach. Since we can't "go back" in a singly-linked list, we must think creatively about how to remove the node. Here’s how we can accomplish this:

  1. Copy the value of the next node into the node that we are asked to delete. This essentially overwrites the current node's value with its next node's value.
  2. Set the current node’s pointer to skip the next node and point to the node after next. This effectively removes the next node from the list and decreases the overall node count.

Example Analysis

  • In the first example, where the linked list is [4,5,1,9] and the node to delete is 5:

    1. Replace 5 with 1 (the next node's value).
    2. Now our list looks like [4,1,1,9].
    3. Remove the next '1' from the list by altering the pointers, resulting in [4,1,9].

  • In the second example, with the same list but needing to delete the node with value 1:

    1. Replace 1 with 9 (the next node's value).
    2. Adjust the list to become [4,5,9].

This method ensures that the structure before and after the node remains unaffected, while effectively removing the node's presence in the list. It’s a clever use of limited access to achieve the desired list manipulation.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    void removeNode(ListNode* currNode) {
        currNode->val = currNode->next->val;
        currNode->next = currNode->next->next;
    }
};

The provided C++ solution involves a function named removeNode that deletes a node from a linked list without given access to the head of the list. This operation is achieved by directly modifying the current node to be deleted.

Here's a breakdown of how this solution works:

  • Assign the value of the next node to the current node. This essentially overwrites the current node's value with the next node's value.
  • Set the next pointer of the current node to the next node's next pointer. This effectively removes the next node from the list by bypassing it, thus deleting the appearance of the current node since its value has been replaced.

This approach presumes that the node to be deleted is not the last one in the list, as it requires access to the next node to work effectively. Moreover, the function needs a non-NULL currNode to avoid runtime errors.

java 
class Solution {

    public void removeNode(ListNode currentNode) {
        // Replace the value of the current node with the value of the next node
        currentNode.val = currentNode.next.val;
        // Point the current node's link to the next node's next link
        currentNode.next = currentNode.next.next;
    }
}

The provided Java solution focuses on a method to delete a node from a linked list without being given access to the head of the list. Specifically, the method targets a node to be removed and operates directly on it. Ensure you pass the node that you want to delete as the parameter to the removeNode method.

This method involves two main operations:

  • The value of the node that is meant to be removed (referred to as currentNode) is replaced with the value of its succeeding node (currentNode.next.val).
  • Then, the link of currentNode is updated to skip the next node, effectively connecting currentNode directly to the next-to-next node (currentNode.next.next).

This approach only works if the node to be deleted is not the last node in the linked list as it relies on the existence of a successor node to copy the value from. This solution leaves the list integrity intact by seamlessly removing the specified node with minimal disruption and no need for traversal from the list's head.

python 
class Solution:
    def removeNode(self, currentNode):
        currentNode.val = currentNode.next.val
        currentNode.next = currentNode.next.next

The provided Python solution demonstrates how to delete a node from a linked list without direct access to the head node. This method operates directly on the node that is required to be removed, often understood as having access only to the node to be deleted in a singly-linked list. The process involves copying the value of the next node into the current node and then adjusting the current node's reference to skip over the next node, effectively deleting it:

  • First, set the value of the currentNode to the value of currentNode.next.
  • Then, update currentNode.next to currentNode.next.next, which removes the next node from the chain by skipping over it.

Remember, ensure the node you are trying to delete is not the last node of the list as it would require a different approach since currentNode.next would be None. This solution effectively bypasses the need to traverse the list from the head to find and remove the node.

Comments

No comments yet.