递归删除具有指定数据的链表

Question

我想递归地删除一个链表。我想到了如何迭代地做到这一点，但我对如何做到这一点很好奇。到目前为止我有：

void deleteNodeRecursively(LinkedList *list, int value){
  Node *curr=list->head;
  if (list->head==NULL){
    return;
  }

  else if (list->head->data==value){
    Node *x=list->head->next;
    delete list->head;
    list->head=x;
  }
   else{
    LinkedList *newlist;
    newlist->head=list->head->next;
    deleteNodeRecursively(newlist,value);
  }
}

我定义的地方

struct LinkedList{
   Node *head;
};

struct Node{
   int data;
   Node *next;
};

如果需要，我可以去掉头部，但我不知道如何去掉身体或尾巴，然后正确地缝合列表，更不用说递归地做了。我该如何进行？为什么这样不行？

编辑：删除问号并替换为我认为可行的代码。

Answer 1

假设你的节点数据有一个“正确的”构造函数和析构函数。

您必须跟踪删除地址，为此您可以传递双指针或对指针的引用。

void deleteNodeRecursively(Node** list, int value){
//                             ^^^ double pointer to track address withing recursive call
  Node *curr= *list ; 
  if (curr ==NULL){ // Base case for recursion 
    return;
  }

  else if ( curr->data==value){ // If node to be deleted is found
    *list = curr->next; // Update the address for recursive calls
    delete curr; // Delete this current "got" node
  }

 // Else simple recurse into 
  deleteNodeRecursively( &(*list)->next, value );
}

注意：此实现将删除数据与值匹配的所有节点。