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

Question

У меня есть проблема с базовым связанным списком, которую я попытался решить ниже. Я был бы признателен за любые входы в мой подход, правильность алгоритма (и даже стиль кодирования). Проблема вызывает функцию, которая удаляет все вхождения int в круговом связанном списке и возвращает любой узел из списка или NULL (когда список имеет значение 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; 
} 

Answer 1

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

Кроме того, использование Node* node в качестве параметра, вместо того, чтобы Node* &node, который позволит предотвратить не-lvalues ​​от прохождения в.

P.S. Забыли точку с запятой после определения структуры? :)

Answer 2

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

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

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

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