Delete Node in a Linked List

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

class Solution {
public:
    void removeNode(ListNode* currNode) {
        currNode->val = currNode->next->val;
        currNode->next = currNode->next->next;
    }
};