Начальный код такой:

{% highlight java %}

public static class LinkedListNode {

public String value;
public LinkedListNode next;

public LinkedListNode(String value) {
    this.value = value;
}

}

LinkedListNode a = new LinkedListNode(“A”); LinkedListNode b = new LinkedListNode(“B”); LinkedListNode c = new LinkedListNode(“C”);

a.next = b; b.next = c;

deleteNode(b);

{% endhighlight %}

Забегая вперед

Мы сможем сделать это за O(1) по сложности и по O(1) по памяти! Ответ будет хитрый и будет работать не на всех входных данных…

Размышляем

Первое, что приходит в голову - это пройтись по всем узлам списка с начала до искомого узла. Но по условию у нас нет головного узла, у нас есть только ссылка на удаляемый узел.

Подождите-ка, как мы вообще удалим узел, если у нас нет ссылки на первый узел?

Мы сделаем так, что указатель предыдущего узла пропустит удаляемый узел, и будет указывать на узел, следующий за удаляемым. Так узлы выглядят до удаления:

VALUEVALUEVALUENEXTNEXTNEXTNone140Удаляемыйузел

Так будут выглядеть узлы после удаления:

VALUEVALUEVALUENEXTNEXTNEXTNone140Удаляемыйузел

Нам нужно как-то пропустить текущий узел и перейти к следующему узлу. Но у нас же нет доступа к предыдущему узлу!

Что если кроме как перенаправлять указатель с предыдущего узла существует другой способ перепрыгнуть с предыдущего значения на следующий?

Что если мы изменим значение текущего узла вместо удаления его?

Решение

Мы скопируем значение и указатель следующего узла в удаляемый узел. Получится, что предыдущий узел будет пропускать удаляемый узел и указывать на следующий узел.

Так связный список выглядел до применения функции:

VALUEVALUEVALUENEXTNEXTNEXTNone382Удаляемыйузел

После будет выгдядеть вот так:

VALUEVALUEVALUENEXTNEXTNEXTNoneNone322Удаляемыйузел

В некоторых языках, например в С нам потребовалось бы руками удалять скопированный узел. Но в Java есть сборщик мусора, который сам позаботится об этом.

{% highlight java %} public void deleteNode(LinkedListNode nodeToDelete) {

// get the input node's next node, the one we want to skip to
LinkedListNode nextNode = nodeToDelete.next;

if (nextNode != null) {

    // replace the input node's value and pointer with the next
    // node's value and pointer. the previous node now effectively
    // skips over the input node
    nodeToDelete.value = nextNode.value;
    nodeToDelete.next  = nextNode.next;

} else {

    // eep, we're trying to delete the last node!
    throw new IllegalArgumentException("Can't delete the last node with this method!");
}

} {% endhighlight %}

Есть две проблемы в нашем решении:

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

  • Второе, метод может выдавать неожиданные результаты. Возьмем такой код:

{% highlight java %} LinkedListNode a = new LinkedListNode(3); LinkedListNode b = new LinkedListNode(8); LinkedListNode c = new LinkedListNode(2);

a.next = b; b.next = c;

deleteNode(b); {% endhighlight %}

Есть несколько побочных эффектов:

  • Не существует эффективного способа переписать ссылки с входящего узла на следующий узел. Например, мы “удалили” узел который хранит ссылку на переменную b, но на самом деле, мы лишь присваиваем узлу новое значение(2) и новую ссылку next. Если мы имеем другой указатель на b откуда-нибудь из другой части кода и мы предполагаем, что объект имеет свое старое значение(8), что может привести к багам.
  • Если существуют указатели на следующий узел за входящим узлом, то эти указатели будут указывать на “висячие узлы” (узел, который не достижим из связного списка). В примере выше, узел c будет “подвешан”. Если мы поменяем c, мы никогда не достигнем это новое значение, двигаясь с головы связного списка до хвоста.

Сложность

O(1) по времени и O(1) по дополнительной памяти.

Источник