c++ - 递归地从链表中删除数据

Question

我有一个链表定义为

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

struct LinkedList{
   Node *head;
};

我想递归地遍历我的链接列表并删除具有指定数据类型的节点(并正确地重新加入节点)。我想出了如何迭代地执行此操作，但我正在努力递归地执行此操作。这就是我到目前为止所得到的:

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

 }
}

基本上，我的策略是判断头部是否有数据。如果是这样，那么我就用下一个节点替换头部。问题是我的 else 语句，我知道我必须“移动”到下一个节点。我不仅要移动到下一个节点，而且我必须确保它是 LinkedList 格式，这样我才能正确使用头部。我不知道如何在不删除所有列表的情况下继续前进。我对制作拷贝有模糊的想法？我不太确定现在该做什么。

编辑:我不想编辑我的结构定义，因为我正在将它们用于我的其他程序。

Answer 1

有很多方法可以做到。

我个人遵循一种简单的方法，即在调用递归函数之前处理头部检查。

if(list->head->data == value)
{
    Node* temp = list->head;
    list->head = list->head->next;
    delete temp;
}
if(list->head != null)
    deleteNodeRecursively(list->head,list->head->next,value);

你的递归函数应该是这样的，

void deleteNodeRecursively(Node* parent, Node* child, int value){
if (child == NULL){ // if null that means end of the list
    return;
}
if( child->data == value)
{
    parent->next = child->next; // attach the parent with the next of child. Thus removes the child form the list
    delete child; // clear the dynamically allocated memory
    deleteNodeRecursively(parent,parent->next,value);
}
else
    deleteNodeRecursively(child,child->next,value); // move to the next
}

附加 如果可以避免递归，就避免递归。因为如果列表足够长，它会在到达末尾之前耗尽你的全部堆栈内存。