Можно ли удалить последний узел в связанном списке?

Например, есть упражнение, которое говорит:Можно ли удалить последний узел в связанном списке?

Написать функцию для удаления узла из связанного списка, учитывая только что указатель

И это решение:

void deleteNode(Node* toDelete) { 

    // this function essensially first copies the data from the next pointer 
    // and then, deletes the next pointer 
    // However, it doesn't work if trying to delete the last element in the list 

    Node *temp = toDelete->next; // create a temp, assign to the one after toDelete 
    toDelete->data = temp->data; // change toDelete's data to the one's after it 
    toDelete->next = temp->next; // change toDelete's next to the one's after it 

    delete temp; 
    temp = nullptr; 
}

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

источник

2013-08-07 Oleksiy

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

Это ничего не значит? это следующий nullptr – Oleksiy

Так что, возможно, вы можете использовать эту информацию, чтобы сделать что-то другое для этого узла. – juanchopanza

Очевидно, что вы не можете; предыдущий узел указывает на действительный узел, и нет возможности изменить это.

Что вы можете сделать, так это добавить узел дозорника в конец списка. Вы никогда не удаляли бы этот узел и никогда не использовали его для хранения данных. Тогда ваше решение будет работать для всех узлов данных. Это не требует каких-либо изменений в структуре узла, но требует изменений в том, как вы перебираете список.

источник

2013-08-07 07:20:46

Интересно, будет ли это запрещено в разделе «Мне не разрешено изменять структуру» или нет. Я предположил, что это будет, но я даю вам +1, если предположить, что это не будет :-) –

Нет, это невозможно с помощью одного списка.

Причина в том, что вам нужно изменить предпоследний узел (чтобы сделать его next указатель нулевым). Но нет способа найти этот узел из последнего узла.

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

Что вы сейчас делаете, это, по сути, «чит», так как вы на самом деле не удаляете указанный указатель. Вы мутируете список, а затем удаляете преемника указанного узла. Это имеет значение, если какой-либо другой бит кода где-то держит указатель на этот преемник при вызове этой функции - их указатель становится недействительным. Таким образом, вы удаляете указанный элемент данных, но вы не удаляете указанный указатель.

источник

2013-08-07 07:18:10

Чтобы быть ясным: это применимо ко всем узлам, а не только к последнему, верно? – juanchopanza

@juanchopanza: согласен. Я редактировал, чтобы сказать это, но потом я объяснил, почему текущий код пользователя может выглядеть так, будто он удаляет указанный узел, но на самом деле этого не делает. –

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

  +-----+ +----------+ +------+ 
header----->|  |->| toDelete |->|  | 
      +-----+ +----------+ +------+

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

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

Node* before = header; 
for (;before->next != toDelete; before = before->next) {;}

сейчас делают before->next = toDelete->next если toDelete последний узел, это будет nullptr иначе указатель на следующий узел

(конечно, вы должны удалить то, что toDelete точки в обоих случаях)

источник

2013-08-07 07:38:11

+1 для искусства ASCII – Hulk

Можно ли удалить последний узел в связанном списке?

ответ

Смежные вопросы