C++链表实现栈的pop函数删除尾节点后出现随机值如何修复

你的pop函数仅释放了尾节点的内存，没有修改尾节点前驱节点的next指针，导致该指针成为野指针，指向已被释放的内存空间，所以访问时会出现随机值，链表的节点删除逻辑实际没有完成。

调整遍历逻辑，同步记录尾节点和它的前驱节点，释放尾节点后将前驱节点的next指针置空，修复后的代码如下：

int pop(stack* s)
{
    if (!isEmpty(s))
    {
        stack* prev = s;
        stack* curr = s->next;
        // 遍历到尾节点，prev记录尾节点的前驱节点
        while (curr->next != NULL)
        {
            prev = curr;
            curr = curr->next;
        }
        // 释放尾节点内存
        delete curr;
        // 前驱节点的next置空，避免野指针
        prev->next = NULL;
        return 1;
    }
    return -1;
}

你当前采用尾插尾删的方式实现栈，每次pop操作都需要遍历整个链表，时间复杂度为O(n)。如果改成头插头删的实现逻辑，push和pop的时间复杂度都可以降到O(1)，运行性能会更好。

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