C++ 中通过递归实现链表填充

Question

我想学习品特并引用它们。我将使用以下任务作为示例。 我需要从给定的数字填充下面定义的链接列表，其中每个数字都是列表的节点。

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

号码是1234。

因此链表看起来像：4 -> 3 -> 2-> 1

我已经实现了利用递归来设置

value

和

next

节点的功能。

void nodeFromNumber(int& number, ListNode* node) {
        node->val = number % 10;
        if (number) {
            ListNode newNode {};
            node->next = &newNode ;

            number /= 10;
            nodeFromNumber(number, &newNode );
        }
    }

问题似乎是我无法将正确的指针从

node->next

设置为实际的

node

。我想了解有关指针主题的更多信息，看起来我无法理解为什么将指针设置为新创建的

node

对象的内存地址（据我所知它已正确分配）会解决错误。在通过

printList

函数遍历列表并打印节点的值后，我发现第一个节点存储了正确的

value

但其余节点则不然（即使我递归设置了

newNode->val

）。 我将在下面提供完整的程序。

#include <iostream>

using namespace std;

void nodeFromNumber(int& number, ListNode* node) {
    if (number) {
        node->val = number % 10;
        ListNode newNode {};
        node->next = &newNode;
        number /= 10;
        nodeFromNumber(number, &newNode);
    }
}

void printList(ListNode* node) {
    if (node == nullptr) {
        cout << "\nlist ended";    
    } else {
        cout << node->val << endl;
        printList(node->next);
    }
}

int main()
{   
    ListNode node1 {ListNode(3)};
    ListNode node2 {ListNode(3, &node1)};
    ListNode headOdList{ListNode(9, &node2)};

    int number { 1234 };
    ListNode head{};
    nodeFromNumber(number, &head);
    
    cout<<"\nList:\n";
    //case A
    //printList(&head);
    //case B
    printList(&headOdList);
    return 0;
}

案例A：正在打印手动创建的链表。

情况 B：正在打印生成的链表，问题是它正在 forrever 循环中运行，并且列表中的第二个

node

具有随机

value

。

你能帮我调查一下吗？谢谢！

回答： 不正确的对象生命周期管理导致了此问题。正确的 `nodeFromNumber() 实现如下：

void nodeFromNumber(int& number, ListNode* node) {
    node->val = number % 10;
    number /= 10;
    if (number) {
        ListNode* newNode = new ListNode;
        node->next = newNode;
        nodeFromNumber(number, newNode);
    }
}

Answer 1

主要问题是您使

next

成员指向局部变量的地址，一旦函数返回，该地址将不再是有效地址。

使用

new

创建节点。

此外，由于您有一个接受值参数和下一个指针的构造函数，因此您可以大大减少代码。

如果您不要求函数的调用者必须提供第一个节点，它也会更加优雅。相反，让函数返回它创建的列表。

建议代码：

ListNode* nodeFromNumber(int number) {
    return new ListNode(
        number % 10, 
        number / 10 ? nodeFromNumber(number / 10) : nullptr
    );
}

在您的主代码中，您可以像这样使用它：

    ListNode *head = nodeFromNumber(1234);
    printList(head);

如果您可以控制整个程序，请不要忘记删除节点。如果您只是在代码挑战网站上编写一个函数并且它必须返回列表，那么您当然不会删除节点并将其留给平台代码来清理。