Ошибки и случаи, приводящие к аварии/неправильному поведению
- Если передан пустой список (head == nullptr): в начале делается `cur = head` и затем `while(cur->next)` — будет разыменование nullptr → авария.
- При удалении последнего узла: после `delete tmp; cur = cur->next;` получится `cur == nullptr`, и следующая итерация делает `while(cur->next)` — разыменование nullptr → авария.
- Последовательные совпадающие узлы сразу после `cur`: код удаляет первый, затем делает `cur = cur->next` (теперь `cur` указывает на следующий удаляемый узел), но сравнивает только `cur->next->value`, поэтому второй совпадающий узел пропускается — логическая ошибка (не все вхождения удаляются).
- API-ошибка: функция принимает `head` по значению и никогда не меняет указатель на голову в вызывающем коде, поэтому узлы в начале списка с нужным `val` не удаляются. Это может привести к неправильному поведению или косвенной утечке памяти, если вызывающий код позже потеряет доступ к этим узлам.
Исправленная реализация (удаляет все вхождения, корректно обрабатывает голову)
Вариант, возвращающий новый head (рекомендуется):
```
Node* remove_all(Node* head, int val) {
Node dummy; // временная "фиктивная" голова
dummy.next = head;
Node* cur = &dummy;
while (cur->next) {
if (cur->next->value == val) {
Node* tmp = cur->next;
cur->next = tmp->next;
delete tmp;
} else {
cur = cur->next;
}
}
return dummy.next;
}
```
Альтернатива — менять голову через ссылку:
```
void remove_all(Node*& head, int val) {
while (head && head->value == val) {
Node* tmp = head;
head = head->next;
delete tmp;
}
Node* cur = head;
while (cur && cur->next) {
if (cur->next->value == val) {
Node* tmp = cur->next;
cur->next = tmp->next;
delete tmp;
} else {
cur = cur->next;
}
}
}
```
Пояснение исправлений
- Использование фиктивной головы или передача `head` по ссылке устраняет спецслучай удаления реальной головы.
- При удалении мы НЕ двигаем `cur` вперед в том же шаге; двигаем `cur` только если не удалили узел. Это позволяет корректно удалить подряд идущие совпадения и не получить `cur == nullptr` до проверки цикла.
- Перед входом в цикл проверяется `head` (в варианте с ссылкой) — не будет разыменования nullptr.
Сложность
- Время: $\mathrm{O}(n)$ — проход по списку один раз.
- Память: $\mathrm{O}(1)$ дополнительной памяти.