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

LeetCode uses this node shape:

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

Function shape:

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

Examples

Example 1:

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

The list starts as:

4 -> 5 -> 1 -> 9

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

After deletion:

4 -> 1 -> 9

Example 2:

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

The list starts as:

4 -> 5 -> 1 -> 9

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

After deletion:

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:

4 -> 5 -> 1 -> 9

we would change the previous node’s pointer:

4.next = 1

Then the list becomes:

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:

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:

4 -> 1 -> 1 -> 9

Now skip the next node:

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.

node.val = node.next.val

2. Skip the next node.

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:

node -> next_node -> rest

The algorithm first copies:

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:

node.next = next_node.next

So next_node is skipped.

The resulting local structure is:

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

Implementation

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:

node.val = node.next.val

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

This line skips the next node:

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.

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:

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()