以递归方式删除指定数据的链接列表

我想递归删除链接列表。我想到了如何迭代地做到这一点，但我很好奇如何做到这一点。到目前为止，我有：以递归方式删除指定数据的链接列表

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

我可以删除头如果需要的话，但我无法弄清楚如何清除体内或反面，然后正确地缝合起来该列表，更不用说递归地进行。我如何继续？为什么这不工作？

编辑：删除问号，并代之以我认为会工作的代码。

来源

2017-08-14 Ayumu Kasugano

首先，您需要一个递归算法，然后才能匹配一个函数。提示：它可能需要一个'Node **'和'int'参数。 – WhozCraig

如果您有问号，为什么不能将deleteNodeRecursively（＆list，value）并最终在null时返回？看起来你有基本情况和“所有其他情况”，只需要继续调用它 –

当然，我不能这样做，因为只是回想起我的功能会一遍又一遍地检查相同的头节点。 –

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

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

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

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

来源

2017-08-14 04:03:46 P0W

同意，就这么简单。 –

如果我有一个curr-> head，这怎么能实现？我不需要跟踪'头部'是什么吗？ –

@AyumuKasugano您必须将开始节点传递给'deleteNodeRecursively'，这在大多数情况下将会是_'root'_/_'head'_节点 – P0W

以递归方式删除指定数据的链接列表

回答

相关问题