Рассмотрите следующий фрагмент на Python для удаления дубликатов из отсортированного связного списка:
def remove_duplicates(head):
node = head
while node.next:
if node.value == node.next.value:
node.next = node.next.next
node = node.next
return head
Найдите и объясните ошибку(и), предложите исправление и оцените временную и пространственную сложность

6 Окт в 10:38
9 +1
0
Ответы
1

Ошибка(и)

Не обрабатывается случай пустого списка. Если head is None — обращение node.next в while сразу вызовет AttributeError.В коде всегда выполняется node = node.next, даже когда мы удалили соседний узел. Это может привести к двум проблемам:
Если при удалении мы установили node.next = None, то присваивание node = node.next сделает node == None, и при следующей итерации while node.next вызовет AttributeError.Правильнее продвигать указатель node только когда текущий узел окончательно не имеет дубликатов справа. Обычно при удалении дубликата лучше остаться на том же узле и проверять вновь новый node.next (в противном случае можно логически пропустить проверки).

Исправление
Надёжный и стандартный вариант — идти по списку и продвигать node только если соседний узел не является дубликатом; если дубликат — удалить его и остаться на том же узле:

def remove_duplicates(head):
if head is None:
return None
node = head
while node and node.next:
if node.value == node.next.value:
node.next = node.next.next # удаляем дубликат, не двигая node
else:
node = node.next # двигаем node только когда следующий различен
return head

Объяснение корректировки

Проверка if head is None предотвращает ошибку при пустом списке.Условие while node and node.next безопасно.Если найден дубликат, мы убираем его связью node.next = node.next.next и остаёмся на том же node, чтобы проверить, не идут ли ещё одинаковые элементы подряд.Если соседний узел не дубликат — двигаем указатель дальше.

Сложности

Временная сложность: O(n), где n — число узлов (каждый узел рассматривается/переустанавливается не более фиксированное количество раз).Дополнительная память: O(1) — алгоритм ин‑плейс, использует константный объём вспомогательной памяти.

Пример
Для списка 1->1->1->2 исправленный алгоритм даст 1->2; для пустого списка вернёт None.

6 Окт в 11:00
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир