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

Ответ 1

Висячий указатель:

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 2

Шаги:

• Скопировать данные из Node (i + 1) в Node (i)
• Скопируйте NEXT второго Node (i + 1) во временную переменную.
• Теперь удалите второй Node (i + 1)//он не требует указателя на предыдущий node.

Функции:

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

Ответ 3

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

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;
}

Ответ 4

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

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

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

Ответ 5

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

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

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

Ответ 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);
     }

Ответ 7

void deleteNode( Node * ptr)
{
    Node *temp = ptr;
    ptr = ptr->next;
    temp->data = ptr->data;
    temp->next = ptr->next;
    free(ptr);
}

мы не можем перемещать обратное направление одиночного связанного списка. Удаление node означает освобождение этой памяти. Так просто скопируйте следующий node контент в заданный указатель (адрес памяти) и освободите следующий node. Это решит вашу проблему.. Спасибо..