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

Question

Название довольно понятное. Вот функция, которую я написал для этой цели:

void wipeLoneCells() 
{ 
    cell *tmp; 

    tail = head; 
    while (1) 
    { 
     if (head == tail && !tail->flag) 
     { 
      head = head->next; 
      free(tail); 
      tail = head; 
      continue; 
     } 

     tmp = tail->next; 

/***/ if (tmp->next == NULL && !tmp->flag) 
     { 
      tail->next = NULL; 
      free(tmp); 
      break; 
     } 
     else if (!tmp->flag) 
     { 
      tail->next = tmp->next; 
      free(tmp); 
      continue; 
     } 

     tail = tail->next;  
    } 
} 

голова и хвост в списке являются глобальными, и список построен к тому времени эта функция вызывается с головой, указывая на первый узел и хвост указывает на last (чей следующий NULL). Я почти уверен, что мой связанный список построен правильно, так как я могу печатать их без ошибок. Иногда эта функция работает отлично, и иногда она приводит к нарушению доступа на линии, помеченной звездочками. Я знаю, что это не совсем так, потому что я получаю результат, который я хочу, когда он не вызывает ошибку, хотя я часто получаю ошибку, поэтому я должен упускать из виду. Спасибо заранее за любую помощь.

EDIT: Вот фиксированный код:

void wipeLoneCells() 
{ 
    cell *tmp; 

    tail = head; 
    while (1) 
    { 
     if (head == tail && !tail->flag) 
     { 
      head = head->next; 
      free(tail); 
      tail = head; 
      continue; 
     } 

     tmp = tail->next; 

     if (tmp->next == NULL && !tmp->flag) 
     { 
      tail->next = NULL; 
      free(tmp); 
      break; 
     } 
     else if (tmp->next == NULL) 
     { 
      tail = tmp; 
      break; 
     } 
     else if (!tmp->flag) 
     { 
      tail->next = tmp->next; 
      free(tmp); 
      continue; 
     } 

     tail = tail->next;  
    } 
} 

Answer 1

Что делать, если

tmp = tail->next; 

NULL это? Следующая строка пытается разыменовать указатель NULL, что приводит к неопределенному поведению - возможно, приведет к сбою.

Вы должны проверить это условие и принять соответствующие меры.

Answer 2

Правильный deleteitem() в односвязный список должен выглядеть следующим образом:

Вы можете избежать рекурсии и придумать итерационной версии (дать ему попробовать, но дайте мне знать, если вам нужна помощь). Я бы не использовал while(1) для этого случая!

typedef struct node { 
    int data; 
    struct node *next; 
}NODE; 


/* 

(1) deleting head 
    delete element and adjust head pointer 

(2) deleting tail 
    delete element and adjust tail pointer 

(3) one element list 
    if data is the data for the only element 
    then delete the list and set head and tail 
    pointers to NULL 

(4) all the other cases 
    traverse through the list and hold the 
    previous pointer. delete element and adjust 
    the next pointers. 

(5) if not the above cases, then element not 
    present.. do nothing.. 

*/ 
void deleteitem(int data) 
{ 
    printf("%s: %d - ", __FUNCTION__, data); 
    NODE *cur = head; 
    NODE *prev = cur; 
    NODE *temp = NULL; 

    if (head == NULL) { 
     assert (tail == NULL); 
     printf("Empty list \n"); 
     return; 
    } 

    if (head->data == data) { 
     temp = head; 

     // one element list 
     if (head == tail) 
      head = tail = NULL; 
     else 
      // list has more than one element 
      head = head->next; 

     printf("%d \n", temp->data); 
     free(temp); 
     deleteitem(data); 
     return; 
    } 

    while (cur != NULL) { 
     if (cur->data == data) { 
      if (cur == tail) { 
       tail = prev; 
      } 
      prev->next = cur->next; 
      printf(" %d deleted\n", cur->data); 
      free(cur); 
      assert(tail->next == NULL); 
      deleteitem(data); 
      return; 
     } 
     prev =cur; 
     cur = cur->next; 
    } 

    printf(" %d not found\n", data); 
    return; 
}