Topics › Linked List › Medium Problems of LL

Delete Node in a Linked List O(1)

Medium TUF ID 258 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a reference to a node node inside a singly linked list. You are not given the head of the list. The node is guaranteed not to be the tail, and all values in the list are distinct. Delete the given node, meaning that after your function returns:

• the value of node no longer appears in the list,
• the list has one node fewer,
• all other values keep their original relative order.

The function returns nothing; the judge rebuilds the list from its own reference to the head and checks the values.

Constraints: the list has 2 to 1000 nodes, values fit in an int, and node is never the last node.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Example 1

list = 4 -> 5 -> 1 -> 9, node = the node holding 5
after the call: 4 -> 1 -> 9

Example 2

list = 4 -> 5 -> 1 -> 9, node = the node holding 1
after the call: 4 -> 5 -> 9

Why this is unusual. Ordinary deletion in a singly linked list needs the predecessor: you stand on the node before the target and write prev.next = target.next. Here there is no head, and singly linked nodes have no back pointers, so the predecessor is unreachable. No amount of walking forward from node will ever bring you back to it.

The way out is to notice what is actually being judged. Nobody checks which ListNode objects survive; the list is judged by the sequence of values seen from the head. So instead of removing the node object, you can make the sequence of values look exactly as if it had been removed. Both approaches below do that, and they differ in how much work they do.

Approach 1: Brute force, shift every value left

Intuition. Think of deleting from an array: you shift every later element one slot to the left and then shrink the array by one. You can do the same here. Copy each successor’s value into the current node, walking towards the end, so every value after node moves one position earlier. The last node now holds a duplicate of the value just before it, so cut it off. To cut the last node you need to stand on the second-to-last node, which is why the loop stops there.

Algorithm.

1. Set cur = node.
2. While cur.next.next exists (so cur is not yet second-to-last): copy cur.next.val into cur and move cur forward.
3. Now cur is the second-to-last node: copy the tail’s value into it and set cur.next = null.

static void bruteForce(ListNode node) {
    ListNode cur = node;
    while (cur.next.next != null) {              // stop on the second-to-last node
        cur.val = cur.next.val;
        cur = cur.next;
    }
    cur.val = cur.next.val;                      // final shift
    cur.next = null;                             // the old tail is now a duplicate: drop it
}

The guarantee that node is not the tail is what makes cur.next.next safe to evaluate on the first check.

Complexity. Time O(k), where k is the number of nodes after node; deleting near the head costs a full pass. Space O(1).

This works, but it touches every later node. Looking closely at what the loop does reveals that almost all of that work is unnecessary.

Approach 2: Optimal, copy the next value and bypass it

Intuition. After the very first shift in the brute force, node holds the value of node.next, so that value appears twice in a row. The list would be correct right now if only the second copy, node.next, disappeared. And deleting node.next is an ordinary deletion, because we are standing on its predecessor: node.next = node.next.next. The shifting of all the later values was never needed.

Put another way: you cannot delete yourself, but you can become your successor and delete the successor instead.

Algorithm.

1. Let victim = node.next (it exists because node is not the tail).
2. Copy victim.val into node.
3. Set node.next = victim.next, removing victim from the chain.
4. Optionally set victim.next = null so the removed node does not keep pointing into the list.

static void optimal(ListNode node) {
    ListNode victim = node.next;
    node.val = victim.val;                       // this node takes over the next node's value
    node.next = victim.next;                     // and the next node disappears from the chain
    victim.next = null;                          // optional: detach the removed node completely
}

Dry run on 4 -> 5 -> 1 -> 9 with node holding 5 (brackets mark node):

Complexity. Time O(1): three assignments regardless of list length. Space O(1).

In Java the bypassed node becomes unreachable and the garbage collector reclaims it. In a language with manual memory management you would free victim explicitly after unlinking it.

Edge cases and pitfalls

• The tail cannot be deleted this way. There is no successor to copy from, and making the tail disappear requires changing its predecessor’s next, which you cannot reach. That is why the problem guarantees node is not the tail. Setting the tail’s value to some sentinel is not deletion.
• Deleting the first node. Works unchanged. The head object stays where it is and takes over the second node’s value, so the caller’s head reference is still valid and now shows the new first value.
• Smallest legal list. In 1 -> 2, deleting the first node leaves 2. Both methods handle it: the brute force skips its loop and goes straight to the final shift.
• Node identity changes. The value node held is gone, but the object node is still in the list, now carrying its successor’s value, while the successor object is gone. Any outside code holding a reference to that successor now holds a detached node. In data structures that keep external pointers into a list (an LRU cache’s hash map, iterators), this trick breaks those references, and you must use a real deletion through the predecessor or a doubly linked list instead.
• Distinct values. The guarantee only makes the judge’s check unambiguous. The algorithm itself works the same with duplicates.

Related problems

• Deletion of the head of LL shows the normal case, where you do control the pointer to the first node.
• Delete the middle node in LL deletes through the predecessor, found with slow and fast pointers.
• Remove Nth node from the back of the LL uses a gap of two pointers to stand on the predecessor.
• Find Middle of Linked List is the companion problem from the same day of the SDE sheet.