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

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

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

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