# 3.10 Deletion Patterns

Deletion removes one or more nodes from a linked list by changing links around them. The values stored in the nodes are usually irrelevant. What matters is the predecessor of the node being removed and the successor that must remain reachable afterward.

In a singly linked list, deletion is harder than insertion because a node does not know its predecessor. For this reason, most deletion algorithms maintain a `prev` pointer, use a sentinel node, or both.

## Delete After a Known Node

The simplest deletion removes the node immediately after `prev`.

```text
if prev.next != null:
  prev.next = prev.next.next
```

This runs in O(1) time. It assumes that `prev` itself is still part of the list.

If the removed node must be detached explicitly, save it first.

```text
node = prev.next

if node != null:
  prev.next = node.next
  node.next = null
```

The important invariant is that `prev.next` must point to the first node after the removed node.

## Delete the Head

The head has no predecessor, so it needs separate handling unless a sentinel is used.

```text
if head != null:
  head = head.next
```

This is correct, but it creates special cases in larger algorithms. A sentinel removes that difference.

```text
dummy.next = head
prev = dummy
cur = head
```

After the algorithm finishes, return:

```text
dummy.next
```

## Delete First Matching Node

Remove the first node whose value equals `target`.

```text
dummy = new Node()
dummy.next = head

prev = dummy
cur = head

while cur != null:
  if cur.value == target:
    prev.next = cur.next
    cur.next = null
    break

  prev = cur
  cur = cur.next

return dummy.next
```

The loop invariant is:

```text
prev.next == cur
```

This invariant gives the algorithm a uniform deletion rule. Even when `cur` is the original head, `prev` is the dummy node.

## Delete All Matching Nodes

When deleting multiple nodes, `prev` advances only when the current node is retained.

```text
dummy = new Node()
dummy.next = head

prev = dummy
cur = head

while cur != null:
  if cur.value == target:
    next = cur.next
    prev.next = next
    cur.next = null
    cur = next
  else:
    prev = cur
    cur = cur.next

return dummy.next
```

This distinction is essential. After deleting `cur`, the predecessor remains the same because the next node has not yet been examined.

For example, deleting `2` from:

```text
1 -> 2 -> 2 -> 3 -> null
```

must produce:

```text
1 -> 3 -> null
```

If `prev` moves after the first deletion, the second `2` may be skipped.

## Delete by Predicate

Deletion by predicate generalizes deletion by value.

```text
dummy = new Node()
dummy.next = head

prev = dummy
cur = head

while cur != null:
  if remove(cur):
    next = cur.next
    prev.next = next
    cur.next = null
    cur = next
  else:
    prev = cur
    cur = cur.next

return dummy.next
```

The predicate may check value, position, frequency, membership in a set, or a structural property.

## Delete the Nth Node from the End

Use a fixed gap between two pointers. A sentinel makes deletion of the head uniform.

```text
dummy = new Node()
dummy.next = head

lead = dummy
follow = dummy

for i in 1..n+1:
  lead = lead.next

while lead != null:
  lead = lead.next
  follow = follow.next

node = follow.next
follow.next = node.next
node.next = null

return dummy.next
```

The gap is `n + 1`, so when `lead` reaches `null`, `follow` points to the predecessor of the node to delete.

## Delete Duplicates from a Sorted List

If the list is sorted and duplicate values should be collapsed to one node:

```text
cur = head

while cur != null and cur.next != null:
  if cur.value == cur.next.value:
    node = cur.next
    cur.next = node.next
    node.next = null
  else:
    cur = cur.next

return head
```

This keeps the first node in each duplicate run.

For:

```text
1 -> 1 -> 2 -> 3 -> 3 -> null
```

the result is:

```text
1 -> 2 -> 3 -> null
```

## Delete All Duplicate Values from a Sorted List

Sometimes every value that appears more than once must be removed completely.

For:

```text
1 -> 1 -> 2 -> 3 -> 3 -> 4 -> null
```

the result should be:

```text
2 -> 4 -> null
```

Use a sentinel and skip whole runs.

```text
dummy = new Node()
dummy.next = head

prev = dummy
cur = head

while cur != null:
  duplicated = false

  while cur.next != null and cur.value == cur.next.value:
    next = cur.next
    cur.next = next.next
    next.next = null
    duplicated = true

  if duplicated:
    next = cur.next
    prev.next = next
    cur.next = null
    cur = next
  else:
    prev = cur
    cur = cur.next

return dummy.next
```

The important point is that `prev` advances only after a non-duplicate value is confirmed.

## Delete a Known Node Without Head

Some interview problems give a pointer to a node but not the head of the list. In a singly linked list, the node cannot be removed directly unless it is not the tail. The workaround copies the successor value and bypasses the successor.

```text
delete_given_node(node):
  if node == null or node.next == null:
    error

  next = node.next
  node.value = next.value
  node.next = next.next
  next.next = null
```

This does not remove the given node object. It removes the next node and mutates the given node to look like it. This distinction matters when node identity is observable.

## Complexity Summary

| Pattern                          | Time | Space |
| -------------------------------- | ---: | ----: |
| Delete after known node          | O(1) |  O(1) |
| Delete head                      | O(1) |  O(1) |
| Delete first match               | O(n) |  O(1) |
| Delete all matches               | O(n) |  O(1) |
| Delete by predicate              | O(n) |  O(1) |
| Delete nth from end              | O(n) |  O(1) |
| Delete duplicates in sorted list | O(n) |  O(1) |

## Common Failure Modes

The most common deletion bug is moving `prev` after deleting `cur`. When a node is removed, `prev` should still point to the last retained node.

Another common bug is failing to update `head` when the removed node is the first node. A sentinel removes this case by making every real node have a predecessor.

A third bug is dropping a suffix by writing `cur.next = null` before saving `cur.next`. The safe order is:

```text
next = cur.next
prev.next = next
cur.next = null
cur = next
```

## Key Insight

Deletion is predecessor control. In a singly linked list, you rarely delete "the current node" directly. You delete the node after a predecessor by changing one edge. A sentinel gives the head a predecessor, and the invariant `prev.next == cur` makes deletion uniform.