Удалить 10000-й узел в связанном списке
У меня есть связанный список из n узлов, я хочу удалить k-й узел и отобразить элемент в нем. Это легко, если значение n относительно мало и сложность проблемы не является проблемой.
Проблема в том, что у меня есть n узлов в связанном списке, где n >=200000, и я хочу удалить узел, который также является относительно большим значением (скажем, k=150000).
Обычным решением этой проблемы является обход всего связанного списка и удаление узла (где сложность решения O(n)), хотя это прямое и простое решение, требующее больше времени. Другое решение этой проблемы может иметь 2 указателя, но это не является оптимальным решением.
Я ищу решение, которое является оптимальным и обеспечивает результат за минимальное количество времени.
Надеюсь, мой вопрос ясен. Нужна помощь..
3 ответа
Используйте концепцию SkipList.
Это похоже на использование скоростных трасс или автомобильных дорог, чтобы добраться до нужного узла с максимально возможной скоростью (выбирая минимальную длину прохождения).
Вам нужно создать несколько слоев, чтобы можно было без колебаний пропустить некоторые узлы.
TC: то же среднее время выполнения, что и у дерева двоичного поиска O(log n),
Не требует сложной реорганизации данного связанного списка.
У вас есть связанный список, поэтому у вас есть доступ O(n). Я вижу два варианта: изменить ваш контейнер или использовать дополнительный контейнер для ускорения прямого доступа (увеличить сложность пространства). Вы не найдете магический контейнер с O(1) сложность для всех видов лечения.
В стандартном связанном списке нет способа (без дополнительных указателей) быстро получить доступ к элементам позже в списке, поскольку единственная ссылка на упомянутые элементы происходит в элементе, непосредственно предшествующем ему.
Если вы знаете, что вам часто требуется доступ к элементу, индекс которого известен, вероятно, лучше просто использовать массив. (Хотя перечитывание вопроса, это все равно не поможет удалить элемент)