237. Delete Node in a Linked List

LeetCode задача 237

Задача

Написать функцию для удаления узла (за исключением хвостового) в односвязном списке, дан только доступ к этому узлу.

Подсказки

1. Обычно, для удаления узла из односвязного списка, нам нужен доступ к предыдущему узлу. В этом случае, у нас такого доступа нет. Как это обойти?

Подход

Поскольку доступа к предыдущему узлу нет, мы не можем просто “вырезать” текущий узел. Однако мы можем переписать значение текущего узла значением следующего узла и затем удалить следующий узел.

Алгоритм

1. Перезаписываем значение текущего узла значением следующего узла.
2. Удаляем следующий узел.

Решение

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

def deleteNode(node):
    node.val = node.next.val    # Перезаписываем значение узла значением следующего узла
    node.next = node.next.next  # Удаляем следующий узел