# LeetCode 237: Delete Node in a Linked List

## Problem Restatement

We are given a node in a singly linked list.

We are not given the `head` of the list.

We need to delete the given node from the linked list.

The important guarantee is that the given node is not the tail node. So `node.next` always exists.

LeetCode defines deletion here as making the linked list behave as if the given node was removed: the value of the given node should no longer exist, the list length should decrease by one, and the order of all other values should remain unchanged. The list values are unique, and the number of nodes is between `2` and `1000`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | The node to delete |
| Output | Nothing |
| Given head? | No |
| Tail node? | The given node is guaranteed not to be the tail |
| Operation | Modify the linked list in place |

LeetCode uses this node shape:

```python
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
```

Function shape:

```python
class Solution:
    def deleteNode(self, node):
        ...
```

## Examples

Example 1:

```text
Input:  head = [4,5,1,9], node = 5
Output: [4,1,9]
```

The list starts as:

```text
4 -> 5 -> 1 -> 9
```

We are given direct access to the node with value `5`.

After deletion:

```text
4 -> 1 -> 9
```

Example 2:

```text
Input:  head = [4,5,1,9], node = 1
Output: [4,5,9]
```

The list starts as:

```text
4 -> 5 -> 1 -> 9
```

We are given direct access to the node with value `1`.

After deletion:

```text
4 -> 5 -> 9
```

## First Thought: Normal Linked List Deletion

Normally, to delete a node from a singly linked list, we need the node before it.

For example, to delete `5`:

```text
4 -> 5 -> 1 -> 9
```

we would change the previous node's pointer:

```text
4.next = 1
```

Then the list becomes:

```text
4 -> 1 -> 9
```

But this problem does not give us the head.

So we cannot walk from the head to find the previous node.

We only have the node itself.

## Key Insight

We cannot remove the current node directly, because we cannot update the previous node's `next` pointer.

But we can make the current node look like the next node.

Suppose the list is:

```text
4 -> 5 -> 1 -> 9
```

and we are given the node with value `5`.

The next node has value `1`.

First, copy the next node's value into the current node:

```text
4 -> 1 -> 1 -> 9
```

Now skip the next node:

```text
4 -> 1 -> 9
```

The original node object still exists, but its value changed from `5` to `1`.

From the outside, the value `5` disappeared from the list, and the list length decreased by one.

That is exactly what the problem asks for.

## Algorithm

Given `node`:

1. Copy the next node's value into `node`.

```python
node.val = node.next.val
```

2. Skip the next node.

```python
node.next = node.next.next
```

That is the whole algorithm.

It works only because the given node is guaranteed not to be the tail.

## Correctness

Let the given node be `node`, and let its next node be `next_node`.

Before the operation, the local structure is:

```text
node -> next_node -> rest
```

The algorithm first copies:

```python
node.val = next_node.val
```

So the value originally stored in `node` disappears from the list, and `node` now contains the value that used to be in `next_node`.

Then the algorithm changes:

```python
node.next = next_node.next
```

So `next_node` is skipped.

The resulting local structure is:

```text
node -> rest
```

The values before `node` are unchanged because the algorithm never touches them.

The values after `next_node` are unchanged because the algorithm preserves `next_node.next`.

The list has one fewer reachable node because `next_node` is bypassed.

Therefore, the linked list behaves exactly as if the original given node value was deleted.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` | Only two assignments |
| Space | `O(1)` | No extra data structure |

## Implementation

```python
class Solution:
    def deleteNode(self, node):
        node.val = node.next.val
        node.next = node.next.next
```

## Code Explanation

This line copies the next value into the current node:

```python
node.val = node.next.val
```

This removes the old value of `node` from the visible linked list.

This line skips the next node:

```python
node.next = node.next.next
```

After that, the next node is no longer reachable from the list.

## Testing

For local testing, we need helper functions to build a list, find a node, and convert the list back into an array.

```python
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def build_list(values):
    dummy = ListNode(0)
    cur = dummy

    nodes = {}

    for value in values:
        cur.next = ListNode(value)
        cur = cur.next
        nodes[value] = cur

    return dummy.next, nodes

def to_list(head):
    ans = []
    cur = head

    while cur:
        ans.append(cur.val)
        cur = cur.next

    return ans
```

Now test the solution:

```python
def run_tests():
    s = Solution()

    head, nodes = build_list([4, 5, 1, 9])
    s.deleteNode(nodes[5])
    assert to_list(head) == [4, 1, 9]

    head, nodes = build_list([4, 5, 1, 9])
    s.deleteNode(nodes[1])
    assert to_list(head) == [4, 5, 9]

    head, nodes = build_list([1, 2, 3, 4])
    s.deleteNode(nodes[3])
    assert to_list(head) == [1, 2, 4]

    head, nodes = build_list([0, 1])
    s.deleteNode(nodes[0])
    assert to_list(head) == [1]

    head, nodes = build_list([-3, 5, -99])
    s.deleteNode(nodes[-3])
    assert to_list(head) == [5, -99]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Delete `5` from `[4,5,1,9]` | Standard example |
| Delete `1` from `[4,5,1,9]` | Delete middle node near tail |
| Delete `3` from `[1,2,3,4]` | Larger list |
| Delete `0` from `[0,1]` | Minimum length list |
| Delete `-3` from `[-3,5,-99]` | Negative values |