Code Implementation

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next
      

// Definition for singly-linked list.
// struct ListNode {
//     int val;
//     ListNode *next;
//     ListNode(int x) : val(x), next(nullptr) {}
// };

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

// Definition for singly-linked list.
// public class ListNode {
//     int val;
//     ListNode next;
//     ListNode(int x) { val = x; }
// }

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
};
      

Problem Description

You are given the head of a singly linked list, and a node that is not the tail node in this list. Your task is to delete the given node from the linked list. However, you are not given access to the head of the list — only to the node to be deleted.

• You must delete the node in-place, meaning you cannot create a new list or copy all the elements.
• There is always at least one node after the one provided (i.e., node.next is not null).
• There is only one valid solution for each input.
• You may not reuse any node values or elements.

Thought Process

At first glance, deleting a node from a singly linked list usually requires knowing the previous node, so you can update its next pointer to skip the node being deleted. However, in this problem, we are not given access to the head or any previous nodes — only to the node that needs to be deleted.

This restriction forces us to think differently. Since we can't access the previous node, we can't change its next pointer. But, since the node to be deleted is not the last node, we can access its next node. Instead of removing the current node, what if we overwrite its value with the value of the next node, and then remove the next node instead? This way, the effect is as if we deleted the current node.

Solution Approach

The solution leverages the fact that we can access the node to be deleted and its next node. Here's how we achieve the deletion:

1. Copy the value of the next node into the current node. This makes the current node's value identical to the next node.
2. Update the next pointer of the current node to skip the next node and point to the node after next. This effectively removes the next node from the list.

By doing this, the current node now contains the data of the next node, and the next node is gone from the list. The linked list behaves as if the original node was deleted.

• Design Choice: We do not need to traverse the list or know the previous node, since we are only modifying the given node and its immediate neighbor.
• Why not just delete this node? In a singly linked list, you can't delete a node if you can't access the previous node. But by copying the next node's value, we "shift" the list left by one at the point of deletion.

Example Walkthrough

Let's walk through an example. Suppose the linked list is:

4 -> 5 -> 1 -> 9

You are given the node with value 5 (not the head), and you need to delete it.

1. Before: The list is 4 -> 5 -> 1 -> 9.
2. Step 1: Copy the value of 5.next (which is 1) into 5. Now the list is 4 -> 1 -> 1 -> 9.
3. Step 2: Update 5.next (now holding value 1) to point to 5.next.next (which is 9). The list is now 4 -> 1 -> 9.
4. Result: The node that originally had value 5 is now gone, and the list is as if 5 was deleted.

Time and Space Complexity

• Brute-Force Approach: If we had access to the head, we would traverse the list to find the previous node, which would take O(n) time.
• Optimized Approach (This Solution): Since we only perform a constant number of operations (copy value and update pointer), the time complexity is O(1).
• Space Complexity: No extra space is used, so the space complexity is O(1).

This is optimal for this problem, since we are only modifying the given node and its neighbor.

Summary

In summary, the key insight is to recognize that in a singly linked list, if you can't access the previous node, you can still "delete" a node by copying the next node's value and skipping over it. This approach is both time and space efficient, requiring only two simple operations. The elegance of the solution comes from its simplicity and the clever use of in-place modifications.