Связанный список, удаляющий узел из определенной позиции путаницы

Question

Итак, скажем, у нас есть этот связанный список: a-> s-> d -> f, и мы хотели удалить d.

У меня возникли проблемы с пониманием того, почему этот код ниже правильно удаляет элемент из связанного списка, и почему приведенный ниже код не дает одинаковых результатов?

Правильный код:

public void deleteNode(ListNode node) { 
    node.val = node.next.val; 
    node.next = node.next.next; 
} 

Неверный код:

public void deleteNode(ListNode node) { 
     node = node.next;//d now points to f 
     //So wouldn't node s.next now equal f 
     //because we have changed what node d references to? 
} 

Спасибо!

Answer 1

Важно понимать, что первый код не на самом деле «удалить Node„D“» (как предполагает название), но вместо этого удаляет значение д.

Это делается путем копирования значения из следующего узла («f» в вашем примере) в текущий узел (узел, который ранее содержал «d»), а затем удаляет следующий узел (узел, содержащий «f»,), который больше не нужен, потому что у нас есть копия значения в текущем узле.

a -> s -> d -> f 
a -> s -> f -> f 
a -> s -> f 

Я считаю, что немного запутываю, я лично удаляю узел «d», не перемещая ни одного контента. Я предполагаю, что это было сделано, чтобы лучше разделить поиск и удаление узлов. Если вы действительно хотели удалить определенный узел (а не его содержимое), вам понадобится ссылка на его предыдущий узел. Это может усложнить интерфейс.

Второй код выходит из строя именно из-за этой проблемы. Он пытается удалить данный узел, но он не может, поскольку его удаление означает обновление члена .next предыдущего узла, к которому у нас нет доступа. Заявление в неправильном коде просто изменяет ссылку в переменной local, которая не влияет на фактический список.