C++刷题必知：为什么链表节点要用new？栈对象与堆对象的本质区别

1. 先看一个最常见的场景：链表的节点为什么省不掉 new

力扣上刷题的人基本都见过这种画面：题解里动不动就是 TreeNode* root = new TreeNode(0)，ListNode* cur = new ListNode(1)，到处都是 new。不少刚从 Java 或者 Python 转过来的同学会问：为什么非要指针 + new 创建类对象？直接 TreeNode root(0) 不也能创建对象吗？

这个问题其实问得非常好，因为它背后涉及的正是 C++ 里栈对象和堆对象的根本区别，也直接决定了你能不能写出不出问题、能交上去的链表和二叉树代码。我在带新人刷题、看群友代码的时候，发现大部分人第一次写链表原地反转、二叉树遍历时崩过一次，后面就长记性了——但很多人只记住了"要用 new"，没搞懂为什么。今天就把这件事彻底说清楚。

1.1 链表和树这类结构，天生离不开"自引用"

先看力扣题里最常出现的定义：

cpp复制struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

注意这里 next 是什么类型？它不是 ListNode，而是 ListNode*，是一个指向 ListNode 的指针。为什么要用指针？因为链表的核心就是"把一个节点和另一个节点关联起来"，这个关联关系必须能跨越函数、跨越作用域，还要能被反复修改。

打个比方，链表就像火车车厢之间的挂钩。一节车厢不能把自己"包含"进另一节车厢里——如果 next 的类型是 ListNode，那一个节点内部又包含另一个节点，另一个节点内部又包含下一个，无限嵌套下去，编译器根本算不出 sizeof(ListNode) 是多少，直接报错。

所以自引用结构只能用指针或者引用。引用一旦绑定不能改，不能重新指向别的节点，做链表增删非常难受。于是指针就成了唯一顺手的选择。而一旦你持有的是指针，构造这个节点的时候，几乎必然要用 new 来创建堆对象。为什么？看下面这个反面教材就明白了。

1.2 如果不用 new，会出什么事

很多新手第一次写链表会这么干：

cpp复制ListNode* buildList() {
    ListNode node1(1);   // 栈上的局部对象
    ListNode node2(2);
    node1.next = &node2;
    return &node1;
}

从语法上看，这段代码是编译通过的。但运行时就是灾难。node1 和 node2 是栈上的局部对象，buildList 函数一返回，这两个对象就自动析构了，内存内容随时可能被覆盖。调用方拿到一个指向"已失效内存"的指针，也就是悬空指针（dangling pointer），打印 val 可能碰巧是 1，也可能是一串垃圾值，多跑几次就段错误。

在力扣上，这个问题表现为：本地测试全对，提交之后换一个测试用例就崩，或者明明逻辑正确却超时——因为悬空指针让程序读到了错误的内存，死循环了。

这就是为什么链表、二叉树这类题目里，新建节点几乎永远是 new ListNode(x) 或者 new TreeNode(x)：因为只有 new 创建出来的对象不依赖函数栈帧，它活在堆上，函数返回了它也还在。

2. 栈对象和堆对象，生命周期差了一个宇宙

要真正理解"为什么用 new"，必须把栈和堆这两个概念刻在脑子里。C++ 不像 Java，Java 里对象都是 new 出来、由垃圾回收器管理；C++ 里你有两种完全不同的创建对象的途径，选择哪种，直接决定对象的生死。

2.1 栈对象是"自动挡"，作用域结束就没

ListNode node(1); 这种写法创建的是栈对象。它的生命周期跟随作用域：进入所在的大括号，它被构造；执行到作用域末尾，它自动析构，内存自动归还。整个过程不需要程序员干预，很省心，但省心的代价是你控制不了它活多久。

实际感受一下：力扣的接口，比如 ListNode* reverseList(ListNode* head)，函数里你创建的局部节点，等这个函数 return 之后全都没了。如果你的算法要让节点"活到函数调用结束之后"，栈对象天然做不到。

再看另一种情况。假设你在一个循环里处理数据：

cpp复制vector<ListNode*> ans;
for (int i = 0; i < n; ++i) {
    ListNode node(i);
    ans.push_back(&node);  // 危险！存的是同一个地址
}

这个错误更隐蔽。循环每轮都会重新构造 node，理论上每轮的地址应该不同，但很多编译器会优化，让每一轮循环复用同一块栈内存——于是 ans 里存了 n 个相同的地址，最后指向同一个对象，逻辑全乱。我见过不止一个人在这种场景下排查了一晚上。

2.2 new 是"手动挡"，活多久自己说了算

new ListNode(x) 做的事是两步：先在堆上分配 sizeof(ListNode) 大小的内存，再调用构造函数初始化这块内存，最后返回这块内存的地址。对象一旦创建在堆上，它的生命周期就从"跟随作用域"变成了"跟随你的 delete"。

也就是说：只要你不在函数末尾 delete 它，函数返回之后它依然存在。链表才能从一个函数里构建好，传回给调用方继续使用。

给一个直观的对照表：

理解了这张表，你就明白了：在 LeetCode 链表题里，你要的不是"在当前函数里能用一下"的节点，而是一个"拼好之后能整条传出去"的结构，所以只能用 new。

3. 在力扣场景里，指针还承担了三个不可替代的职责

很多人以为指针就是为了配合 new 用的，其实反了。指针是语言本身的机制，new 只是一种"让对象长期存活"的创建方式。在刷题场景里，指针本身至少有三种不可替代的作用，理解了这些，你才不会在"到底用不用指针"上犹犹豫豫。

3.1 递归结构必须靠指针才能表达

树和链表的数据结构定义本身是递归的：一棵树由根节点、左子树、右子树组成，而子树又是一棵树。C++ 的结构体里不能无限嵌套自身，所以只能用指针把子结构"指"出来。

如果没了指针，你没法定义 TreeNode，更没法写递归的 maxDepth、inorderTraversal。这是指针在"表达数据结构"层面上的作用，跟 new 不 new 没关系——哪怕你从力扣接口拿到的是一棵已经构建好的树，访问它也必须通过指针。

递归遍历的时候，参数传 TreeNode* root 而不是传值，也有性能上的考量。传值意味着把整个节点复制一份，而且树的子节点指针还得跟着复制，浪费时间。传一个指针只复制 8 字节的地址，递归深度再大也不怕。

3.2 传指针避免整对象拷贝，还能保持"同一份"状态

C++ 默认按值传递，函数参数会做拷贝构造。如果传的是 vector<ListNode>，整个 vector 里的所有节点全部被复制一遍；如果传的是 vector<ListNode*>，复制的只是指针数组，底层节点只有一份。

更关键的是"改得动"的问题。你在函数里 node->val = 100，如果调用方传进来的是指针，调用方的节点确实被改了；如果传进来的是值，你改的只是副本，调用方一无所知。刷题时很多原地算法，比如反转链表、合并两个有序链表，本质就是"修改节点之间的指针关系"，没有指针根本做不了。

顺带提一个经典坑：对象切片（slicing）。把派生类对象直接塞进基类类型的容器，比如 vector<Shape> 里 push 一个 Circle，会发生切片，Circle 特有的成员全被丢弃。而 vector<Shape*> 里存 new Circle，则完全没这个问题。这个特性在力扣的设计模式类题目里经常用到。

3.3 多态与接口抽象

虽然力扣纯算法题大部分时候只碰 ListNode 和 TreeNode，但遇到设计题、迭代器题、模拟 OOP 的题，多态就是核心考点。

cpp复制class SortStrategy {
public:
    virtual void sort(vector<int>& data) = 0;
    virtual ~SortStrategy() = default;
};

class QuickSort : public SortStrategy {
public:
    void sort(vector<int>& data) override { /* ... */ }
};

SortStrategy* strategy = new QuickSort();
strategy->sort(nums);

这里 strategy 必须是基类的指针（或者引用）。如果直接定义一个 SortStrategy strategy 对象，那它根本无法容纳派生类的实现。所以"指针 + new 创建类对象"在这类场景里，不是为了生命周期，而是为了多态本身。

4. new 不是白给的，它附赠三个"义务"

用 new 一时爽，但 C++ 没有垃圾回收，new 出来的每一个对象，理论上都要有人负责 delete。力扣题解里几乎看不到 delete，是因为判题环境特殊，不意味着你在项目里也能这么放肆。

4.1 谁 new 谁负责 delete

所谓 RAII 思想，本质就是"资源随对象生，随对象死"。你手动 new 出一个对象，就得保证在合适的时机 delete 掉它。链表题里经常出现的内存泄漏场景是：你在中间插入了新节点，但后面把这个节点跳过了，没人删它，它就永远留在堆里。

我曾经在本地用 valgrind 排查过一段链表排序代码，每次跑都会泄漏几个节点，量不大，判题看不出来，但在长时间运行的服务里，这种泄漏积累几小时就能把内存吃光。力扣单次进程可能只跑几十毫秒，泄漏几个节点无伤大雅，但这绝对不是一个好习惯。

new 和 delete 必须成对出现，还要注意匹配：单个对象用 delete ptr，对象数组用 delete[] arr。混用属于未定义行为，轻则崩溃，重则堆结构被破坏。

4.2 力扣判题环境的"宽容"与"纵容"

说实话，力扣的 C++ 判题器对内存泄漏很宽容。每个测试用例一般是一个独立进程，跑完进程退出，操作系统把整个进程的内存全部回收。所以你就算一个节点都不删，照样能通过所有测试。

但这带来了一个副作用：许多刷题的人形成了"反正不用管内存"的惯性。等进了真正做 C++ 服务的公司，写的代码要 7×24 小时运行，再抱着这种习惯，线上就会频繁报警——内存占用一步步爬上去，最终 OOM 被 kill。

我自己的策略是：刷题时对自己要求严格一点。凡是自己 new 出来的对象，思路允许的情况下随手 delete。虽然力扣不在乎，但手感和习惯是自己的。特别是写一些需要长时间运行的模拟题（比如 LRU Cache 的某种手写实现），更要注意。

4.3 为什么题解很少用智能指针

你可能要问：既然怕泄漏，为什么题解里不写 unique_ptr<ListNode> 或者 shared_ptr<ListNode>？

原因有几个。第一是代码冗长。力扣接口要求返回裸指针 ListNode*，你要用智能指针，最后还得 release() 把裸指针交出去，写起来绕。第二是性能。智能指针有引用计数等开销，虽然很小，但在超大数据规模的测试用例里，shared_ptr 的原子递增还会引入额外代价。第三是语义问题。链表本身是一种"互相指向"的结构，如果用 shared_ptr 管理节点，节点之间互相持有引用计数，形成循环引用，反而会造成真正泄漏。

所以在面向面试、面向刷题的语境下，裸指针 + new 是大家默认的最简洁写法。但这不意味着智能指针没用，恰恰相反，在工程代码里，我强烈建议能用 unique_ptr 的地方就别裸 new。刷题和工程是两套规则，心里要有这个数。

5. 到底该不该 new：按语义而不是按习惯

很多人刷题刷多了，养成一个坏习惯：看见类对象就 new。其实力扣里大量场景根本不需要 new，滥用反而增加出错面。判断标准不是"是不是类对象"，而是你要的是"值"还是"引用"。

5.1 值语义 vs 引用语义

如果这个对象只是临时算个结果，用完就扔，那栈对象完全够用，别 new。比如实现一个坐标点：

cpp复制struct Point {
    int x, y;
    Point(int a, int b) : x(a), y(b) {}
};

在函数里算两点距离，直接 Point p(1, 2) 就好，不需要 Point* p = new Point(1, 2)。栈对象访问更快，还不用考虑释放，编译器优化起来也更顺畅。

反之，如果这个对象要被放进容器，还得在容器外继续被人使用，或者它本身就是链式结构的一个节点，需要让别的对象长期指向它，那用 new 堆对象才是正确选择。一句话：你需要的是"这个对象本身"就值语义，你需要的是"到对象的通道，且通道要比当前作用域活得久"就引用语义。

5.2 几个典型场景的取舍对照

第三个和第五个是最常见的误用点。vector<Point> 里不要无脑存 Point*，因为 vector 扩容时会拷贝元素，裸指针拷贝后指向的是同一批对象，一旦你 delete 其中一个，另一个副本就悬空了。除非你明确需要多态，否则容器存值才是正道。

5.3 不用 new 也能模拟指针的替代方案

有时候为了避坑，你可以用"数组下标"来模拟指针。力扣上的静态链表、邻接表就是这么做的：

cpp复制const int MAXN = 100000;
int val[MAXN], nxt[MAXN];
int idx = 0;   // 相当于 new 的返回值

int newNode(int x) {
    val[idx] = x;
    nxt[idx] = -1;
    return idx++;  // 返回"指针"，其实只是下标
}

这种情况下，不存在内存泄漏、悬空指针、new 失败等一堆问题，性能还比 new 快不少。尤其在图论题里，vector<vector<int>> 加下标索引，比 vector<ListNode*> 手动管理内存要稳妥得多。我的建议是：当你在力扣上写高频、超大规模的数据结构模拟时，优先考虑数组模拟；当你写的是标准链表面试题时，老老实实用 new 就好。

6. 实战中我踩过的坑：空指针、悬空指针、泄漏速查

这部分是真正的经验值。指针 + new 的组合在刷题时最容易出的三类问题，我一个个说，附带排查思路。

6.1 一访问就崩：八成是空指针或悬空指针

最常见的就是没判空。比如合并两个有序链表，循环里访问 cur->next->val，没确认 cur->next 不为空；或者递归里没处理 root == nullptr 就直接 root->val。LeetCode 的报错通常是 AddressSanitizer: heap-use-after-free 或者 segmentation fault。

碰到这种崩溃，我的排查顺序固定是三步：第一步看函数入口的指针是否可能为 null；第二步检查循环里每次取 next 之前有没有判空；第三步检查自己 return 出去的地址是不是局部对象的地址。大部分崩溃到第二步就能解决。

6.2 运行时结果对，但偶尔崩溃：悬空指针的隐蔽性

更坑的是那种运行十次、九次正确、一次崩溃的代码。比如上面那个在函数里返回局部节点地址的例子，可能在当前测试用例下栈内存恰好还没被覆盖，调用方读到的值是对的。换一个用例，栈上数据一多，地址就被别的函数覆盖了，于是随机崩溃。

这种问题在本地调试时很折磨，因为不是每次都能复现。我的经验是：不要相信"试了几次没问题"，只要代码里有"返回局部对象地址"的模式，直接改成 new。代价只是多一行 delete，换来的是确定的正确性。

6.3 内存泄漏在力扣上为什么容易"看不见"

还有一个常见疑问：我明明每轮循环都 new 新节点，也没人 delete，为什么力扣不报内存泄漏？因为前面说的，单进程跑完即回收。你本地用 valgrind --leak-check=full 跑，会发现一堆 definitely lost 的记录。

在力扣上，泄漏通常表现为"内存占用越来越大"或者极端情况下超时——因为堆越来越大，分配变慢，缓存命中率下降。真遇到这种诡异超时，我会先在本地用 valgrind 查一遍泄漏，顺手把该 delete 的地方补上。虽然大部分时候根因不是泄漏，但这个习惯救过我很多次。

下面给一个速查表，遇到问题直接对号入座：

7. 一点个人实操心得

最后聊点我自己的体会。刚开始学 C++ 刷题那阵，我也是无脑 new，觉得题解怎么写我就怎么写。直到有一次做二叉树的层序遍历，自己在循环里 new 了一堆节点拿来构造辅助队列，结果队列里全是同一个地址，拿出去一测直接死循环，才被迫去翻 C++ 对象生命周期的资料。那一次之后我才彻底明白：栈对象和堆对象不是两种写法的问题，是两种编程语义的问题。

现在我的习惯是写代码之前先问自己三句话：这个对象需要活多久？谁最后释放它？我拿到的是值还是通道？这三句话想清楚，指针和 new 的用法基本就不会错了。

还有一个小建议：刷题归刷题，但手上最好常备一份 C++ 对象模型的资料，把构造函数、析构、拷贝、移动这些底层机制吃透。力扣的题面有标准模板，你复制粘贴也没人拦你，但只有真正理解了背后的"为什么"，你在真实项目里写出的代码才不会是定时炸弹。靠经验和文档支撑的 C++ 水平，才是能带得走的东西。