Алгоритм удаления одного элемента в одном связанном списке со сложностью O (1)

Question

Я студент информатики в Германии. Мой профессор задал следующий вопрос:

'Дана ссылка на узел в одном связанном списке (который не является последним узлом). Дайте алгоритм удаления этого элемента из списка, который имеет сложность O (1) при сохранении целостности '.

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

Я что-то упустил?

Answer 1

Это зависит от того, являются ли узлы изменяемыми (по значению).

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

toDelete.value = toDelete.next.value
toDelete.next = toDelete.next.next

Вся информация из toDelete теперь перезаписана информацией из старой toDelete.next. (В зависимости от платформы вам может понадобиться освободить старый toDelete.next - что означает сохранение временной ссылки на него. Не хорошо, если у кого-то еще есть ссылка на него, конечно. В Java / C # вы просто игнорируй это.)

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

Это зависит от того, что это не последний узел в списке.

Answer 2

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

// pseudocode:
this.data = next.data;
var temp = this.next;
this.next = next.next;
delete temp;

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

Да. Вы сохраняете в качестве итеративного указателя указатель на следующий указатель предыдущего списка.

walk = &head;
while (!match(*walk)) {
    walk = &walk[0]->next;
    if (!*walk) return ;
}
*walk = walk[0]->next;