以遞歸方式刪除指定數據的鏈接列表

我想遞歸刪除鏈接列表。我想到了如何迭代地做到這一點，但我很好奇如何做到這一點。到目前爲止，我有：以遞歸方式刪除指定數據的鏈接列表

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

以遞歸方式刪除指定數據的鏈接列表

回答

相關問題