Рассмотрите следующий фрагмент на 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 Найдите и объясните ошибку(и), предложите исправление и оцените временную и пространственную сложность
Не обрабатывается случай пустого списка. Если 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.
Ошибка(и)
Не обрабатывается случай пустого списка. Если 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.