Delete Node in a Linked List

There is a singly-linked list head and we want to delete a node node in it.

You are given the node to be deleted node. You will not be given access to the first node of head.

All the values of the linked list are unique, and it is guaranteed that the given node node is not the last node in the linked list.

Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean:

• The value of the given node should not exist in the linked list.
• The number of nodes in the linked list should decrease by one.
• All the values before node should be in the same order.
• All the values after node should be in the same order.

Example 1:

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

Output: [4,1,9]

Example 2:

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

Output: [4,5,9]

Constraints:

• The number of 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.

Deleting a Node in a Singly Linked List

This problem presents a unique challenge: deleting a node in a singly-linked list without access to the head. Let's explore the approach and the code implementation.

Approach

Since we don't have access to the head, we can't traverse the list to find the node before the one we want to delete and update its next pointer. Instead, we'll use a clever trick: we'll copy the value of the next node into the node we want to delete, and then skip over the next node, effectively deleting it.

Code Implementation (Python)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def deleteNode(node):
    """Deletes the given node from a singly-linked list."""
    node.val = node.next.val  # Copy the value from the next node
    node.next = node.next.next  # Skip the next node

# Example Usage (for testing)
# Create a linked list: 4 -> 5 -> 1 -> 9
head = ListNode(4)
head.next = ListNode(5)
head.next.next = ListNode(1)
head.next.next.next = ListNode(9)

# Delete the node with value 5
node_to_delete = head.next
deleteNode(node_to_delete)

# Print the modified list (for verification)
current = head
while current:
    print(current.val, end=" -> ")
    current = current.next
print("None")

Code Implementation (Java)

public class DeleteNodeLinkedList {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

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

    public static void main(String[] args) {
        // Example Usage (for testing)
        // Create a linked list: 4 -> 5 -> 1 -> 9
        ListNode head = new ListNode(4);
        head.next = new ListNode(5);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(9);

        // Delete the node with value 5
        ListNode nodeToDelete = head.next;
        deleteNode(nodeToDelete);

        // Print the modified list (for verification)
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

Time Complexity Analysis

O(1) - The operation involves only a few constant-time operations (copying a value and updating a pointer), regardless of the list's size.

Space Complexity Analysis

O(1) - We're not using any extra space that scales with the input size. The algorithm operates in place.

Edge Cases

• Node is the tail: The problem statement explicitly mentions that the node to be deleted will not be the last node in the linked list. If it were, this approach wouldn't work because there would be no next node to copy from.
• Empty List / Invalid Node: While the problem states the node will be in the list, a production-ready solution might include a null check to handle cases where the input node is null or invalid.

Alternative Approach (Brute force, for comparison)

While not applicable given the constraints (no access to the head), a naive approach would involve traversing from the head to find the node before the target node, then updating its next pointer. This would have O(n) time complexity.

Conclusion

The provided solution offers an efficient and elegant way to delete a node from a singly-linked list when direct access to the head is not available. It leverages the ability to modify the node's value and pointer to effectively remove the node from the list.