Problem Overview

You are given a node in a singly linked list, and your task is to delete this node.
You are not given access to the head of the linked list — only the node that needs to be deleted.

It is guaranteed that the node to be deleted is not the last node in the list.

Example 1

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation:
You are given the second node with value 5.
After deleting it, the linked list becomes [4,1,9].

Example 2

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]

---

Intuition / Approach

Normally, deleting a node in a linked list requires access to the previous node — so that we can change its next pointer to skip the node being deleted.

However, in this problem, we do not have access to the previous node or the head of the list.
We are only given the node to be deleted.

So, the usual approach of adjusting pointers from the previous node is not possible.

The clever trick here is:

• Instead of deleting the given node directly,
• We copy the data from the next node into the current node,
• Then we delete the next node.

This makes it look as if the given node was removed from the list, even though technically, the next node was deleted.

---

Algorithm Explanation

Let’s assume:

Linked List: 4 → 5 → 1 → 9  
Node to delete: 5

Steps:

1. Copy value: Copy the value from the next node (1) into the current node (5).
   Now the list looks like: 4 → 1 → 1 → 9
2. Delete next node: Adjust the next pointer of the current node to skip over the next node.
   So, node.next = node.next.next
   The list now becomes: 4 → 1 → 9

Effectively, the original node with value 5 is “gone” from the list.

---

Java Code Implementation

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public class DeleteNodeInLinkedList {

    public void deleteNode(ListNode node) {
        // Copy the data from the next node
        node.val = node.next.val;
        // Bypass the next node
        node.next = node.next.next;
    }

    // Example usage
    public static void main(String[] args) {
        // Create 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);

        DeleteNodeInLinkedList solution = new DeleteNodeInLinkedList();
        System.out.println("Before deletion:");
        printList(head);

        // Delete node with value 5 (second node)
        solution.deleteNode(head.next);

        System.out.println("After deletion:");
        printList(head);
    }

    private static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }
}

---

Step-by-Step Execution Example

Initial Linked List:
4 → 5 → 1 → 9
Node to delete: 5

1. Copy the value from next node (1) → current node becomes 1
   List now looks like: 4 → 1 → 1 → 9
2. Skip the next node (node.next = node.next.next)
   Resulting list: 4 → 1 → 9

Output: [4,1,9]

---

Complexity Analysis

1. Time Complexity:O(1)
   • We only perform a constant number of operations — copying values and adjusting a pointer.
   • No traversal or recursion is required.
2. Space Complexity:O(1)
   • No additional space is used.

This is one of the rare problems where the optimal solution runs in constant time and space.

---

Important Notes and Edge Cases

1. Cannot Delete the Last Node
   • The approach fails if the given node is the last one (node.next == null), because there is no “next” node to copy data from.
   • That’s why the problem explicitly guarantees that the node to delete is not the tail node.
2. The Node Reference Changes Internally
   • The node’s identity in memory remains the same, but its value changes.
   • Technically, the next node is deleted, but from the perspective of the list, it appears that the given node was removed.
3. This Approach Mutates the List
   • The operation modifies the list structure directly; it does not return a new list.

---

Alternative Approach Discussion

If we had access to the head of the list, the standard deletion process would be:

1. Traverse from the head until you find the previous node of the target.
2. Update previous.next = previous.next.next.
3. Allow garbage collection to delete the target node.

However, since the head is not given, this standard approach is not applicable here, and the copy-and-skip trick remains the only valid method.