Delete Node in a Linked List
No predecessor? Become the successor, then delete it instead
Deleting from a singly linked list normally means pointing the previous node past the victim, but here the previous node cannot be reached: links run one way and the head is not provided. What is reachable is the successor. Copying its value into the given node makes the two nodes interchangeable, and unlinking the successor — which the given node CAN do, because it owns that pointer — leaves a list that reads exactly as if the original value had been removed. It only works because the problem promises the node is not the tail; a tail has no successor to impersonate.
Details
Animated on: list = [4, 5, 1, 9], delete the node holding 5 given ONLY that node — no head, no previous node. Result: [4, 1, 9].
Problem:Delete Node in a Linked ListMedium
No predecessor? Become the successor, then delete it instead
step 1 / 9
List = [4, 5, 1, 9]. The only thing handed over is node (value 5, position 1) — no head, no predecessor. A normal delete rewires the node BEFORE the target, and that node is unreachable from here.
- node=1· arr[1] = 5
1FUNCTION deleteNode(node)2 nxt <- node.next3 node.val <- nxt.val4 node.next <- nxt.next5 RETURN
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- List = [4, 5, 1, 9]. The only thing handed over is node (value 5, position 1) — no head, no predecessor. A normal delete rewires the node BEFORE the target, and that node is unreachable from here.
- The predecessor holds value 4, and its next is what actually points at node. But links only go forward: nothing stored in node leads back to it, and walking from head is off the table because head was never given.
- What IS reachable is everything after node. The problem guarantees node is not the tail (tail here is 9), so node.next always exists — that guarantee is exactly what the trick depends on.
- Grab nxt = node.next (value 1). The list [4, 5, 1, 9] minus 5 would look identical to the list minus 1 IF node first took on the value 1. So delete the reachable node instead of the unreachable one.
- node.val <- 1. The value 5 is gone from the list already; positions 1 and 2 now both read 1, so the list is [4, 1, 1, 9] — one duplicate too long. Stopping here is the classic bug: nothing was deleted, only overwritten.
- node.next <- nxt.next skips the duplicate: node now points at 9, and nxt is unlinked. The list is [4, 1, 9]. Two assignments, no traversal, no predecessor — O(1).
- Walking the real links from head to check: cur = 4, next = 1. The node object that used to sit at position 1 is still here — it simply carries a different value now.
- Walking the real links from head to check: cur = 1, next = 9. The node object that used to sit at position 1 is still here — it simply carries a different value now.
- Walking the real links from head one last time: 9 is the tail, and 5 never appeared. Every node is still reachable, so the deletion is a real structural change, not a local variable set to null.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.