Измерение сложности частично зависит от того, что вы считаете своими переменными. Что касается количества узлов в списке, ваш алгоритм занимает O(1) в использовании пространства. Однако в этом случае это может быть не самой лучшей перспективой.
Другая переменная в этой ситуации - это размер узла. Часто этот аспект игнорируется анализом сложности, но я думаю, что он имеет значение в этом случае. Хотя требования к пространству вашего алгоритма не зависят от количества узлов, они зависят от размера узла. Чем больше данных в узле, тем больше места вам нужно. Пусть s будет размером одного узла; было бы справедливо сказать, что требование к размеру вашего алгоритма составляет O(s).
Требование к размеру более распространенного алгоритма для этой задачи равно O(1), даже если учитывается как количество узлов, так и размер каждый узел. (Нет необходимости создавать какие-либо узлы, нет необходимости копировать данные.) Я бы не рекомендовал ваш алгоритм по этому.
Чтобы не было всех негативных, я бы рассматривал ваш подход как два независимых изменения к традиционному. Одним из изменений является введение фиктивного узла new_head. Это изменение полезно (и фактически используется), даже если ваша реализация утечка памяти. Это лишь незначительно менее эффективно, чем использование фиктивной головки, и это упрощает logi c для удаления узлов в начале списка. Это хорошо, если размер вашего узла не слишком велик.
Другим изменением является переключение на копирование узлов вместо их перемещения. Это очень ценное изменение, так как оно добавляет работы программисту, компилятору и выполнению. Анализ Asymptoti c (big-O) может не поднять это дополнение, но оно не принесет никаких выгод. Вы потеряли ключевое преимущество связанных списков и ничего не получили взамен.
Давайте посмотрим, как отбросить второе изменение. Вам нужно было бы добавить одну строку, в частности, инициализируя new_head->next в head, но это уравновешивается удалением необходимости устанавливать tail->next в nullptr в конце. Другим дополнением является предложение else, так что строки, выполняемые в настоящее время на каждой итерации, не обязательно выполняются на каждой итерации. Кроме того, это удаление кода и некоторые изменения имени: удалите указатель temp (используйте вместо него tail->next) и создайте новые узлы в l oop. Взятые вместе, эти изменения строго сокращают объем выполняемой работы (и потребности в памяти) по сравнению с вашим кодом.
Чтобы устранить утечку памяти, я использовал локальный фиктивный узел вместо его динамического выделения. Это исключает последнее использование new, что, в свою очередь, устраняет большинство возражений, высказанных в комментариях вопроса.
Node* deleteAllOccurances(Node *head, int x)
{
Node new_head{-1}; //<-- Avoid dynamic allocation
new_head.next = head; //<-- added line
Node *tail = &new_head;
while(tail->next != nullptr) {
if(tail->next->data != x) {
tail = tail->next;
}
else { //<-- make the rest of the loop conditional
Node *q = tail->next;
tail->next = tail->next->next;
delete q;
}
}
return new_head.next;
}
В этой версии устраняется «фактор ограничения», поскольку для одного узла есть преимущество new не используется. Эта версия достаточно чиста, чтобы подвергнуть ее анализу сложности, и никто не спросит «почему ???».