Удаление узла в круговом связанном списке

У меня есть проблема со связанным списком, которую я попытался решить ниже. Буду признателен за любой вклад в мой подход, правильность алгоритма (и даже стиль кодирования). Проблема вызывает функцию, которая удаляет все вхождения int в круговом связанном списке и возвращает любой узел из списка или NULL (когда список нулевой).

Вот некоторый код C ++, который у меня есть:

struct Node{
Node* next;
int data;
};

Node* deleteNode(Node* &node, int num){

if(!node){
return NULL;
}

Node* given = node;
Node* del;

while(node->next != given){
if(node->next->data == num){
del = node->next;
node->next = node->next->next;
delete del;
}
node = node->next;
}

//Check if the first node needs to be deleted, with variable node pointing to last element
if(given->data == num){
node->next = given->next;
delete given;
}

return node;
}

1

Решение

delete node; должно быть delete del;,

Также используйте Node* node в качестве параметра, а не Node* &node что предотвратит передачу не-значений

постскриптум Забыли точку с запятой после определения структуры? 🙂

1

Другие решения

Не следуя всей вашей логике, я могу сразу увидеть, что этот код не может работать.

Вы проверяете, что список ввода пуст, и это единственный случай, когда ваш код возвращает NULL, Но что произойдет, если вам передадут список, в котором все элементы должны быть удалены?

Эта проблема также имеет тонкость в этом. Чтобы проверить, что вы заполнили циклический список, вам нужно сравнить его с первым адресом, чтобы узнать, не вернулись ли вы к началу. Однако, если этот элемент был удален, то по стандарту C ++ вы даже не разрешается использовать его адрес в сравнении.

Чтобы избежать двух проходов по удаляемым элементам, одним из возможных трюков является «разорвать цикл» при запуске итерации, чтобы вы могли проверить NULL вместо проверки адреса начального узла.

1

По вопросам рекламы [email protected]