Medium

Delete Node in a Linked List

LAB

Given a linked list encoded as an array and the value of the node to delete, return the list after deleting the first matching node. The value is guaranteed to be present and not the tail.

EXAMPLES

Example 1

Input
{
  "head": [
    4,
    5,
    1,
    9
  ],
  "value": 5
}

Output
[
  4,
  1,
  9
]

FUNCTION SHAPE

head: intArrayvalue: int→intArray

SOLUTION NOTE

This solution is clever because it bypasses the need to access the previous node. Instead, we copy the value from the next node and delete that node instead.

Ex: 1 -> 2 -> 3 -> 4

We have access to 2.

We do not have access to 1, so what we can do is:

1 -> 3 -> 3 -> 4

1 -> 3 -> 4

Note, for proper node management we should delete the original 3 node.

Reveal reference solution +

pythonREFERENCE

def deleteNode(self, node):
    # Since we don't have access to the previous node,
    # we can't delete the node directly.
    # Instead, we'll copy the next node's value to
    # the current node and delete the next node

    # Copy the next node's value
    node.val = node.next.val

    # Delete the next node
    del_node = node.next
    node.next = node.next.next
    del del_node

TimeO(1)

SpaceO(1)

Open on LeetCode ↗