deleting multiple 'key' nodes from linked list in C

Question

I am in C and need to deleting multiple occurrences of a 'key' char in a linked list and return the head of the linked list.

This function only works properly if the 'key' is not the first or last node 'char', of the linked list. Examples… using key 'a'

fails: a->d->a->m->NULL (throws error) 
fails: t->a->d->a->NULL (throws error) 
passes: d->a->g->n->a->b->NULL (returns d->g->n->b->NULL )

Also, anything with a 'key' that immediately repeats fails. Examples… using key 'a'

fails: d->a->a->a->a->r->n->NULL (returns d->a->a->r->n->NULL)

-----------------------------delete()---------------------------------------

node* delete2(char key, node* head)
{
   /*IF NULL*/
   if(!head)
   {
      return head;
   }

   node* prev = NULL;
   node* current = head;

   /*if first node(head) is to be deleted*/
   while (current && current->data == key)
   {
      prev = current;
      current = current->next;
      head = current;
      free(prev);
   }


   /*scan list left to right*/
   while (current)
   {
      if (current->data == key)
      {
         prev->next = current->next;
         free(current);
         current = prev->next;
      }
      prev = current;
      current = current->next;
   }

   return head;
}

Answer 1

It should be something like this:

node * remove_key(char key, node * head)
{
    // remove initial matching elements
    while (head && head->data == key)
    {
        node * tmp = head;
        head = head->next;
        free(tmp);
    }

    // remove non-initial matching elements
    // loop invariant: "current != NULL && current->data != key"
    for (node * current = head; current != NULL; current = current->next)
    {
        while (current->next != nullptr && current->next->data == key)
        {
            node * tmp = current->next;
            current->next = tmp->next;
            free(tmp);
        }
    }

    return head;
}

---

As an interesting mental exercise, imagine you had an "exchange" function (like C++ does):

node * exchange(node ** obj, node * newval)
{ node * tmp = *obj; *obj = newval; return tmp; }

Then you could write this code very simply:

node * remove_key(char key, node * head)
{
    while (head && head->data == key)
        free(exchange(&head, head->next));

    for (node * current = head; current != NULL; current = current->next)
        while (current->next != nullptr && current->next->data == key)
            free(exchange(&current->next, current->next->next));

    return head;
}

You could even specialize to some kind of "exchange_with_next":

node * exchange_with_next(node ** n) { return exchange(n, (*n)->next); }

Answer 2

First: prev can be in a undetermined state: you free it in the first while and dereferencing it in the second while when you do prev->next. this is the cause of why the function fail if the key is the first char.

Second: if your key is the last char the following code:

if (current->data == key)
{
    prev->next = current->next;
    free(current);
    current = prev->next;
}
prev = current;
current = current->next;

will fail because you dereferencing current but current is NULL.

Step by step:

if (current->data == key)
{
    prev->next = NULL;// current is the last element so current->next == NULL
    free(current);
    current = prev->next;

}
prev = current;
current = current->next;

if (current->data == key)
{
    prev->next = NULL;
    free(current);
    current = NULL;// because prev->next == NULL
}
prev = current;
current = current->next;

if (current->data == key)
{
    prev->next = NULL;
    free(current);
    current = NULL;
}
prev = NULL;// same again...
current = current->next;

if (current->data == key)
{
    prev->next = NULL;
    free(current);
    current = NULL;
}
prev = NULL;
current = NULL->next;// FAIL!!!