189. Delete Node in a Linked List

You cannot reach the previous node, but you can make this node impersonate its successor: copy the next node's value here, then unlink the next node.

The trick

Deleting a node usually means pointing its predecessor past it. Here you have no predecessor. Instead, overwrite this node with the data of the node after it, then bypass that successor:

node.val = node.next.val    # become a copy of the next node
node.next = node.next.next  # drop the now-duplicate successor

The node object stays in place, but the sequence of values is exactly what you'd get by removing the original node. This is safe because the node is guaranteed not to be the tail, so node.next always exists.

Worked example

List 4 -> 5 -> 1 -> 9, delete the node holding 5. Copy 1 into it (4 -> 1 -> 1 -> 9), then skip the old 1 node (4 -> 1 -> 9).

Complexity

• Time: O(1).
• Space: O(1).

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