c - 从C中的链表中删除多个 'key'节点

Question

我使用 C 语言，需要删除链表中多次出现的“key”字符并返回链表的头。

只有当“key”不是第一个或最后一个节点“char”时，此函数才能正常工作， 的链接列表。示例...使用键“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 )

此外，任何具有立即重复的“ key ”的操作都会失败。示例...使用键“a”

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

----------------------------删除()---------------- ------------------------

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

应该是这样的:

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;
}

---

作为一项有趣的心理练习，想象一下您有一个“交换”函数(就像 C++ 那样):

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

那么你可以非常简单地编写这段代码:

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;
}

您甚至可以专门研究某种“exchange_with_next”:

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