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

Answer 2

第一: prev可以处于待定状态:当您执行prev->next时，您在第一个while中释放它并在第二个while中取消引用它。这就是为什么当键是第一个字符时函数失败的原因。

秒:如果您的密钥是以下代码的最后一个字符:

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

将失败，因为您解引用了current，但current是NULL。

一步一步:

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!!!