为什么我的删除节点功能不起作用？

Question

我检查了板子，找不到任何帮助。我发现在给定基本和一般情况下实现递归函数很容易，但这不是我的工作方式。我应该向下迭代一个链表直到我到达链表的尾部。如果下一个节点为NULL，那么我必须在最后一个节点存储该值，删除该节点，然后返回该值。它类似于dequeue功能，只是它是递归执行的。我做错了什么?

int LinkedList::removeTailRec(Node *n)
{
    // check for the base case(s)
    if(n->next == NULL)
    {
        Node *tmp = new Node();
        tmp = n;
        int val = n->value;
        tmp = NULL;
        return val;
    }
    else
        return removeTailRec(n->next);
    // else call the recursive method
}

Answer 1

首先，我建议您使用nullptr而不是NULL。

然后，进入你的代码。您实际上没有从列表中删除任何内容。

if(n->next == NULL)
{
    Node *tmp = new Node();
                ^^^^^^^^^^
    //Useless, and dangerous. This memory is never free'd
    tmp = n;
    int val = n->value;
    tmp = NULL;
    ^^^^^^^^^^
    //You just set a local variable to NULL, you're not deleting anything
    return val;
}

如果你想删除节点，你必须保持对前一个节点的引用(例如，有一个双重链表，也就是说，在每个节点中有一个指向下一个元素的指针和指向前一个元素的指针，或者直接处理前一个节点)。

将前一个节点的next设置为nullptr，保存节点的值，然后删除Node指针。

一种方法是使用指向下一个节点的指针:

int LinkedList::removeTailRec(Node *n)
{
    //EDIT: Adding a check for n validity
    if(!n){
        //Here, you should have a way of detecting 
        //a call to your method with a null pointer
        return 0;
    }
    Node* nextNode = n->next;
    // check for the base case(s)
    if(nextNode->next == nullptr)
    {
        //Get the next node value
        int val = nextNode->value;
        //Set the current node next member to nullptr
        n->next = nullptr;
        //Free the last node
        delete nextNode;
        return val;
    }
    else{
        return removeTailRec(n->next);
    }
    // else call the recursive method
}

Answer 2

您正在存储结果，但没有从链表中删除它。你可以在另一个变量(指针:result)中返回结果。

Node* getTail(Node *n,int *result){
    //u can even free the memory
    if(!n->next)
    {
       result=n->value;
       return NULL;
    }
    n->next=getTail(n->next,result);
}

或者你可以用其他方式

int getTail(Node *n)
{
    if(!n) return 0;
    if(n->next)
    {
        if(!n->next->next)
        {
            Node *frnode=n->next;
            int result=n->next->value;
            n->next=NULL;
            delete frnode;
            return result;
        }
     getTail(n->next);
}

Answer 3

您没有删除代码中的最后一个节点，并且您在这里泄漏了另一个(临时)节点。要删除最后一个节点，必须将前一个节点中的链接归零。你的代码应该看起来像

...
if (n == NULL || n->next == NULL)
    throw std::out_of_range("node");
if(n->next->next == NULL)
{
    int val = n->next->value;
    delete n->next;
    n->next = NULL;
    return val;
}
else ...

请注意，c++不是一种函数式语言，并且没有对尾递归进行优化，因此在实际应用中，当您的列表变得足够大时，您最终会因为堆栈溢出而失败=)使用Haskell或Erlang进行这种风格的编程，在c++中使用for或while

Answer 4

当n为尾节点时，您应该将节点n的前一个节点的next字段设置为NULL。