從C中的鏈表中刪除多個'key'節點

Question

我在C中，需要在鏈表中刪除多個「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) 

此外，任何帶有「密鑰」的重複立即失敗。示例...使用鍵'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

它應該是這樣的：

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可以在未確定的狀態：在第一個while中釋放它，並在第二個while中取消引用它時prev->next。這是爲什麼如果該鍵是第一個字符時該功能失敗的原因。

二：如果你的關鍵是最後一個字符下面的代碼：因爲你提領current但current

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

將失敗是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!!!