Удаление любого узла из одного связанного списка, когда указывается только указатель на этот узел

Question

Это вопрос, заданный мне в интервью.

"В памяти есть один связанный список. Вы должны удалить узел. Вам нужно написать функцию для удаления этого узла, которая принимает только адрес узла, который будет удален, как входные данные и ничего больше (включая голова) "

Я дал ответ, аналогичный тому, который был дан в ответе ниже - Копирование содержимого следующего узла в удаляемый узел и удаление следующего.

Удаление среднего узла из одного связанного списка, когда указатель на предыдущий узел недоступен

Но интервьюер снова спросил меня, что если я передам адрес последнего узла. Я сказал ему, поскольку следующим будет NULL, скопируйте этот NULL в поле данных вместе с адресом следующего узла, который также является NULL. Затем он сказал мне, что возникнет проблема с висящими указателями ... которую я немного не понял. Кто-нибудь может пролить свет на эту проблему? Есть ли общее решение для этого?

Обновление (два дня спустя): немного больше. Учитывая, что в конце списка нет специального узла. И последний узел указывает на NULL, и если этот узел задан как входной, как сделать так, чтобы предыдущий узел указывал на NULL. Или это невозможно?

Проще говоря: если узел задан в качестве входных данных для функции, как сделать указатель, который ссылается на него, указывает на NULL

Answer 1

Шаги:

1. Копировать данные из узла (i + 1) в узел (i)
2. Скопировать СЛЕДУЮЩИЙ второй узел (i + 1) во временную переменную.
3. Теперь удалите второй узел (i + 1) // для него не требуется указатель на предыдущий узел.

Функция:

void delete_node(node* node)
{
    node->Data = node->Next->Data;
    node* temp = node->Next->Next;
    delete(node->Next);
    node->Next = temp;
}

Answer 2

Dangling Pointer:

(http://en.wikipedia.org/wiki/Dangling_reference)

Висячие указатели и дикие указатели в компьютерном программировании - это указатели, которые не указывают на действительный объект соответствующего типа. Это особые случаиНарушения безопасности памяти.

Повисшие указатели возникают, когда объект удаляется или освобождается, без изменения значения указателя, так что указатель по-прежнему указывает на место в памяти освобожденной памяти. Поскольку система может перераспределитьранее освобожденная память другому процессу, если исходная программа затем разыменовывает висячий указатель (теперь), это может привести к непредсказуемому поведению, поскольку память теперь может содержать совершенно другие данные.

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

(1) Нет внешних ссылок на список,как вы поясните в примечании. (2) Проблема с висящим указателемm может возникнуть, как сказал интервьюер.

Оба (1) и (2) не могут быть правильными одновременно.Это означает, что где-то есть недоразумение.

Об удалении последнего узла:

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

Я думаю, что вы путаете эти две вещи:(1) Указатель p, который указывает на NULL, (2) Узел связанного списка, который имеет NULL в своем поле данных.

Предположим, структура данных a -> b -> c -> d.Запись NULL в поле данных d не будет волшебным образом заставлять c иметь в своем поле next указатель NULL.

Вы можете удалить последний узел , если в связанном списке всегда есть специальный последний узел , который никогда не будет удален.Например, a -> b -> c -> d -> LAST, где LAST имеет специальное значение в своем поле данных, которое обозначает, что это действительно последний элемент.Теперь, чтобы удалить d, вы можете удалить LAST и записать специальное значение в поле данных d.

Возможно, это именно то, что вы пытались сказать во время интервью, и в этом случае между вами и интервьюером должно было быть какое-то недопонимание.

Answer 3

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

void delete_node(node* node1)
{
    node* search=head;
    if(node1==head)
    {
        head=head->next;
        search->next=NULL;
        node1->next=NULL;
    }
    while(search->next != node1)
        search=search->next;
    if(node1->next==NULL)
    {
       search->next=NULL;
    }
    else
    {
       search->next=node1->next;
       node1->next=NULL;
    }
    delete node1;
}

Answer 4

Если есть другие элементы, которые указывают на следующий узел, который будет скопирован на текущий узел и затем удален, то эта операция приведет к ошибке. Таким образом, в своем ответе вы должны были подчеркнуть, что ваше решение работает только при отсутствии внешних ссылок на список.

Ваше решение работает с последним узлом, только если структура данных дополнена конкретным элементом "последний узел". (Если вы используете Smalltalk, вы можете написать self become: nil Ни на одном другом языке нет ничего похожего)

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

Answer 5

Возможно, при обходе списка ссылок может потребоваться, чтобы любой узел, который указывает на null, был null узлом независимо от значения ...

a->b->c->d->NULL

, поэтому d - nullузел и узел не должны рассматриваться как узел.таким образом, вы можете сэкономить на использовании специальных значений, поскольку они не являются правильными в общем смысле.кроме этого у вас не будет другого способа указать предыдущему узлу null.

Answer 6

 public void removeNode(Node node){

        /* if no node return null */
        if(node==null) return;

        /* if only 1 node then delete node */
        if(node.getNext()==null) {
            node = null;
            return ;
        }

        /* copy next node data to this node */
        node.data = node.getNext().data();

        /* store the next next node */
        Node second = node.getNext().getNext();

        /* remove next node */
        removeNode(node.getNext());

        /* set the copied node as next */
        node.setNext(second);
     }