Delete Node in a Linked List
You are given a reference to one node inside a singly linked list — the node to delete — and nothing else: no head, no way to reach the list from the front. Remove that node so the list's values read exactly as if it were gone, in place. Nothing is returned. It is guaranteed the node is not the tail, so a successor always exists.
- The number of nodes in the given list is in the range [2, 1000]
- -1000 <= Node.val <= 1000
- The node to be deleted is in the list and is not a tail node
head = [4,5,1,9], node = 5[4,1,9]head = [4,5,1,9], node = 1[4,5,9]This problem quietly removes the tool you normally rely on. To delete a node from a linked list the ordinary way, you rewire its predecessor — the node before it — to point past it: prev.next = target.next, and the target vanishes from the chain. But here you are given only the target node. You have no head to start from, and a singly linked list has no backward arrows, so from the target there is no way to find the node in front of it. The one operation deletion needs — reach the predecessor — is exactly the one you cannot perform.
It is worth being sure this really is a dead end before abandoning it. Every arrow in the list points forward. Starting at the target you can walk toward the tail, but never toward the head. Nothing you can see references the predecessor. Without the head you cannot even scan from the front to find it. So rewiring the predecessor is genuinely impossible — not merely inconvenient. If we insist on physically removing this particular node, we are stuck.
Here is the turn. The problem never asked us to destroy this specific node object — it asked us to make the list's values read as though the node were gone. Those are different goals. We cannot detach the box we are standing in, but we can rewire the box in front of us, because we hold it: it is target.next, and we are its predecessor. So instead of deleting ourselves, we overwrite ourselves with our successor and then delete the successor. Copy the next node's value into our own node, then splice the next node out. Our node now carries the successor's value and points where the successor pointed — from the outside, indistinguishable from having removed the original node. We deleted a node; it just wasn't the one we were handed.
# Become our successor, then unlink it
node.val = node.next.val # copy the next value into ourselves
node.next = node.next.next # skip over the (now duplicated) next nodenode.next would be null, there would be nothing to copy, and the trick collapses; deleting a tail with no predecessor reference is the one case that is genuinely impossible in a singly linked list. Also notice what actually happens to memory: the node object you were given survives (now wearing its successor's value), and the successor node is the one unlinked. That is fine — the problem cares about the sequence of values, not which physical object holds each one.next to the successor's next, which is the node holding 9. The list now reads 4 → 1 → 9.The whole move is O(1) time and O(1) space — two field writes, no traversal — but the transferable lesson is the reframe, not the speed. When you cannot reach the thing you are asked to change, stop trying to reach it and ask whether you can produce the same observable effect from where you already stand. Here the observable effect was a sequence of values, and shifting a value one node back achieved it without the unreachable predecessor. That habit — separating "what must be true afterward" from "the specific object I assumed I had to modify" — turns a seemingly impossible constraint into a two-line solution.
O(1) Identity Theft
Identify target node (5)