使用双指针的链表出现无限循环问题求助

我不清楚这段代码为何会引发无限循环：调用一次push_frontLL()没有问题，但调用两次后会无限打印数字1。

代码如下：

class Node {
public:
    size_t data;
    Node* next;
    Node() {
        this->data = 0;
        this->next = nullptr;
    }
};
void push_frontLL(Node** &head, int val) {
    Node* newNode = new Node();
    newNode->data = val;
    if (head != nullptr) {
        newNode->next = *head;
    }
    head = &newNode;
}
int main() {
        Node** head = nullptr;
        
        //insert
        push_frontLL(head, 0);
        push_frontLL(head, 1);

        // print
        Node* current = *head;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        return 0 ;
}

我猜测这和push_frontLL()覆盖了之前的节点有关，但不确定具体原因，会不会是因为两次使用了相同的标识符newNode？不过手动插入节点时代码可以正常运行：

// insert
Node* newNode1 = new Node();
newNode1->data = 0;
if (head != nullptr) {
    newNode1->next = *head;
}
head = &newNode1;

Node* newNode2 = new Node();
newNode2->data = 1;
if (head != nullptr) {
    newNode2->next = *head;
}
head = &newNode2;

将插入逻辑放入for循环后，效果和调用push_frontLL()一致，会无限打印最近插入节点的data值：

// insert
for (size_t i = 0; i < 2; i++) {
    Node* newNode = new Node();
    newNode->data = i;
    if (head != nullptr) {
        newNode->next = *head;
    }
    head = &newNode;
}

我希望尽可能继续使用双指针实现，请问这个无限循环问题的原因是什么？

问题核心原因 #

问题出在你把局部变量的地址赋值给了外层的双指针head：

• push_frontLL里的newNode是函数局部变量，存储在栈内存中，函数执行完毕后这块内存会被系统回收释放。
• 执行head = &newNode;时，外层的Node** head被设置为指向这个栈上局部变量的地址。
• 第一次调用函数后，栈内存还未被其他数据覆盖，*head（即新节点的堆内存地址）暂时有效，所以打印操作能正常执行。
• 第二次调用函数时，新的newNode局部变量会复用之前被释放的栈内存地址，此时newNode->next = *head相当于让新节点的next指针指向自己（因为*head现在指向的是新的newNode本身），形成了自循环链表，所以打印时会无限输出1。

手动插入能正常运行，是因为newNode1和newNode2是main函数的局部变量，在打印阶段它们的栈内存还未被释放，head指向的地址始终有效，不会出现指针复用导致的自循环。

修复方案（保留双指针思路） #

不需要使用Node** &head这种引用型双指针，常规的双指针参数写法就足够实现需求：

void push_frontLL(Node** head, int val) {
    Node* newNode = new Node();
    newNode->data = val;
    newNode->next = *head;
    *head = newNode;
}

对应的main函数初始化改为单指针即可：

int main() {
    Node* head = nullptr;
    
    push_frontLL(&head, 0);
    push_frontLL(&head, 1);

    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    return 0 ;
}

如果一定要坚持用Node**类型的head变量，绝对不能让它指向局部变量地址，要让*head始终指向堆上的节点：

void push_frontLL(Node** &head, int val) {
    Node* newNode = new Node();
    newNode->data = val;
    if (head != nullptr) {
        newNode->next = *head;
    }
    // 先给head分配堆上的指针存储位置
    if (head == nullptr) {
        head = new Node*();
    }
    *head = newNode;
}

不过这种写法冗余且没必要，常规的单指针加双指针参数的写法已经足够清晰高效。

内容的提问来源于stack exchange，提问作者BinWiz