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

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
}