Удаление заданного элемента из односвязного списка

Условие

Дан односвязный список с головой head, и требуется удалить из него конкретный узел node. В функции вам будет передан только сам узел node, доступ к голове списка head не будет предоставлен. Все значения в списке уникальны, и гарантировано, что удаляемый узел не является последним элементом.

Требования к удалению:

• После операции значение удаляемого узла не должно присутствовать в списке.
• Количество элементов в списке должно уменьшиться на один.
• Порядок элементов, расположенных перед node, должен остаться неизменным.
• Порядок элементов, расположенных после node, также должен сохраниться.

Тестирование пользователем: Для проверки вам необходимо передать полностью сформированный список head и конкретный узел node, который будет удалён. Узел node гарантировано находится не в конце списка и действительно присутствует в нём. Система построит список, вызовет вашу функцию с указанным узлом и проверит полученный список после выполнения.

Пример 1: Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Explanation: Удаляется второй элемент со значением 5, после чего список становится 4 → 1 → 9.

Пример 2: Input: head = [4,5,1,9], node = 1 Output: [4,5,9] Explanation: Удаляется третий элемент со значением 1, и список преобразуется в 4 → 5 → 9.

Ответ

Скопируйте значение следующего узла в node и перенаправьте node.next через один узел. Это возможно благодаря гарантии, что node не последний.

def delete_node(node):
    if node.next is None:
        raise ValueError('Нельзя удалить последний узел этим способом')
    node.val = node.next.val
    node.next = node.next.next

Для 4 → 5 → 1 → 9 узел со значением 5 получает значение 1 и ссылку на 9, после чего последовательность становится 4 → 1 → 9. Время и дополнительная память — O(1).

Физически из цепочки исключается следующий объект, а не переданный node. Это соответствует условию об удалении значения, но важно при наличии внешних ссылок на конкретные узлы. Без доступа к предшественнику аналогично удалить хвост нельзя.