打 ACM 模式题的时候链表相关的题我见过太多人挂在不该挂的地方不是算法想不出来而是 create、delete 这类辅助函数写得手忙脚乱。尤其是从力扣那种已经帮你建好链表的模式切换到 ACM 格式——输入输出全得自己处理数据也得自己造、自己链、自己释放——不少人第一反应是崩溃。这篇文章就聚焦一件事把链表辅助函数写稳。我会从节点定义讲到建表、删节点、释放整条链配合实际可编译的代码和踩坑记录适合正在刷 ACM 模式题、准备机试或者做数据结构实验的读者。看完你能直接抄走一套模板省得每次都在考场现想。1. 为什么 ACM 格式下必须单独封装链表辅助函数1.1 ACM 格式和日常刷题模式到底差在哪先明确一个概念。力扣、牛客的 核心代码模式 会帮你把测试数据转化成现成的链表头指针你只需要实现一个函数。而 ACM 格式也叫 OJ 模式是另一套玩法题目只给你输入输出格式比如第一行有几个整数、接下来每行表示什么操作你得自己解析输入、手动构建链表、最后自己把结果打印出来。也就是说链表不会凭空出现在你面前它需要你亲手造出来。这个差异直接影响代码组织方式。核心代码模式下链表结构是平台给的你往往只在题目里用到一次ACM 格式下同一道题可能需要多次创建链表、多次删除节点甚至在同一份代码里操作多个链表。如果每次都在主逻辑里临时写创建和删除代码会迅速变成一团浆糊而且非常容易漏释放内存。我见过不少同学在 ACM 模式题里把建表逻辑直接写在 main 函数里建三个链表就要复制三遍循环。一旦代码跑到一半报段错误他根本分不清是建表的问题还是主逻辑的问题。所以我的建议是先把辅助函数当成基础设施来写一次写好反复调用出问题也容易定位。1.2 辅助函数的边界怎么划分辅助函数不是越多越好也不是越少越好。我的划分标准很简单凡是操作链表结构本身的动作都值得封装成函数凡是和具体题目业务相关的逻辑留在主逻辑里。举个例子创建一个新节点是结构操作封装成 createNode按照数组顺序建立一条链表是结构操作封装成 createList把某个值的节点删掉是结构操作封装成 deleteNode而判断两个链表是否相等计算链表中位数这种属于业务逻辑不一定要封装。这样划分之后主函数里看到的都是语义清晰的调用读代码就像读题目描述一样顺畅。另外要注意ACM 格式下内存管理是手动的C 里 new 出来的节点必须对应 delete。如果建表函数和释放函数不对称就会出现泄漏。所以创建和删除一定要成对设计创建函数负责分配删除函数负责回收这一点我在后面会反复强调。2. 节点定义与基础约定动手写代码前的三个决定2.1 结构体定义struct ListNode 的标准写法链表节点定义看起来人人都会但细节上有讲究。ACM 格式题目里节点通常只存储一个整数值和一个后继指针所以我习惯写成这样struct ListNode { int val; ListNode* next; ListNode(int x 0) : val(x), next(nullptr) {} };这里有三点值得说。第一我加了构造函数这样每次 new ListNode(x) 的时候next 指针自动初始化为 nullptr能避免一大类野指针问题。如果不写构造函数new ListNode 只会分配内存val 和 next 都是未初始化的随机值访问 next 就会踩内存。第二默认参数 x 0 让我在不需要具体值的时候可以直接 new ListNode()比如创建哨兵节点。第三我用的是 C 的 struct默认成员公开访问方便用 class 反而要写 public没必要。有些老教材喜欢写 typedef struct LNode { int data; struct LNode* next; } LNode;这是 C 语言的写法C 里直接 struct ListNode 就能当类型名用写法更简洁。如果你在 ACM 比赛里用 C 语言提交那就得用 typedef 那套这个要看你平时刷题的编译器环境。2.2 带不带哨兵节点一个影响所有操作的决策哨兵节点dummy node是链表操作里最实用的技巧之一。它就是一个不存有效数据的虚拟头节点让真正的头节点变成第二个节点。我几乎所有链表辅助函数里都会用哨兵节点原因很简单统一处理头节点被删除或链表为空的边界情况。举个例子删除头节点和删除中间节点的代码逻辑是不同的。没有哨兵节点时你得单独判断如果要删的是头节点就移动头指针否则遍历找前驱。有哨兵节点后头节点也有前驱了一套通用逻辑搞定所有位置。这有点像你排队办事如果前面有个虚拟的0号窗口那每个真实窗口都能用同样的规则处理。当然哨兵节点也有代价多一个节点的内存以及头节点其实是 dummy-next的心智负担。我的建议是辅助函数内部大量使用哨兵节点但函数的输入输出仍然是无哨兵的标准链表。也就是说哨兵是函数内部实现细节不影响到外部调用者。这样既享受了哨兵的好处又不让调用方困惑。2.3 指针传递的约定什么时候用引用链表辅助函数里最常见的 bug 是删了头节点但调用者的头指针没更新。这涉及 C 的传参机制如果你传的是 ListNode* head那么在函数内部修改 head 指向只改了局部变量调用者手里的指针纹丝不动。解法是传引用ListNode* head。这样函数内部对 head 的修改会直接作用到调用者的变量上。我的约定很简单凡是可能修改头指针本身的操作比如 deleteNode、deleteList一律传 ListNode*凡是只遍历、不改变链表结构的操作比如打印链表、求长度传 const ListNode* head 就行。这个约定一旦定下来就不用每次写之前纠结。我见过很多新手在 deleteNode 里删了头节点返回后还拿着旧的头指针去访问结果就是访问到已释放的内存随机报错。传引用是从根源上解决这个问题。3. 创建链表的两种标准姿势与完整实现3.1 单节点创建createNode 为什么值得单独写最基础的辅助函数是创建单个节点。有人觉得一个 new 就搞定的事情没必要封装但实际写题时你会发现createNode 能帮你统一初始化和错误处理的地方省得每处都写 new ListNode(x)。ListNode* createNode(int val) { ListNode* node new ListNode(val); return node; }这个函数虽然短但它承担一个职责保证返回的节点一定是构造完整、next 指向 nullptr的合法节点。在 ACM 实际代码里new 是可能失败的分配失败会抛出 bad_alloc 异常一般比赛环境不处理也行但如果你希望代码更稳可以在里面包一层 try-catch 返回 nullptr。不过比赛场景我一般不这么做保持简单更实际。3.2 尾插法建表保留输入顺序的唯一选择尾插法是最常用的建表方式因为它保持数据原始顺序。核心思路是用一个 tail 指针始终指向当前链表的最后一个节点每来一个新节点就接在 tail 后面然后更新 tail。ListNode* createListByTail(const vectorint nums) { ListNode* dummy new ListNode(0); ListNode* tail dummy; for (int x : nums) { tail-next new ListNode(x); tail tail-next; } ListNode* head dummy-next; delete dummy; return head; }这段代码有个细节很多人会忽略循环结束后我把哨兵节点 delete 掉了。这样返回的链表中不包含哨兵节点调用者拿到的就是标准链表。如果你不删哨兵也能正常工作但链表里就多了一个值为 0 的节点打印时会出现一个多余的 0而且操作顺序全乱。这个错误我见过太多次了。参数用 vector 是我在本地调试的习惯。ACM 题目通常需要从 stdin 读取数据后面我会展示怎么把读取结果转成 vector 再调用这个函数这样逻辑就分层了输入解析归输入解析建表归建表互相不污染。3.3 头插法建表生成逆序链表的技巧头插法和尾插法正好相反每个新节点都插到链表最前面所以最终链表的顺序和输入数据顺序相反。这个性质有时候是特性而不是缺点比如你要构造反序链表或者用栈模拟后进先出的场景。ListNode* createListByHead(const vectorint nums) { ListNode* head nullptr; for (int x : nums) { ListNode* node new ListNode(x); node-next head; head node; } return head; }头插法实现里没有哨兵节点因为每次都在头部插入直接维护 head 指针就够了逻辑本来就简单。我在实际比赛中用头插法的频率低于尾插法但它是单链表逆序问题的基础——你完全可以不交换节点只需要重新遍历原链表做头插就能生成一条逆序的新链表。这个技巧在遇到反转链表类题目时可以秒杀。3.4 从 stdin 构建链表ACM 常用输入组合ACM 题目最常见的输入方式是第一行给节点个数 n第二行给 n 个整数。处理这种输入我通常写成int n; cin n; vectorint nums(n); for (int i 0; i n; i) cin nums[i]; ListNode* head createListByTail(nums);有人会问为什么不直接边读边建表非要先存进 vector 再建表我的理由是解耦题目有时候还会让你根据这些值做其他操作比如查某个值的位置、计算和值。如果数据存在 vector 里这些操作都方便如果只存在链表里想随机访问就得遍历。先用 vector 存一份相当于保留原始数据链表只是其中一种视图。多花一点内存但换来代码灵活性值得。如果是多组数据输入格式类似直到遇到 0 结束或者每组第一行是 n那就在外层套个 while 循环读一次建一次链表用完马上释放。这里尤其要注意多组数据时上一组的链表必须释放干净否则累积内存泄漏会让程序在大量测试用例下越来越慢最终被 OJ 判超时或内存超限。4. 删除操作的两个层次删节点与释放整条链4.1 按值删除节点deleteNode 的通用写法删除指定节点的函数我按删除第一个匹配的节点和删除所有匹配的节点两种需求分别实现。两者核心思路一样都是遍历找目标然后用前驱节点跳过目标节点最后删除。void deleteNode(ListNode* head, int val) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* prev dummy; ListNode* cur head; while (cur) { if (cur-val val) { prev-next cur-next; delete cur; cur prev-next; break; // 只删第一个匹配的如果想删全部去掉 break 即可 } else { prev cur; cur cur-next; } } head dummy-next; delete dummy; }写这段代码的时候有一个关键点当 cur-val val 时一定要先让 prev-next 指向 cur-next再把 cur delete 掉。顺序不能反。如果先 delete curcur-next 已经变成不可访问的悬空指针再取 cur-next 就是访问已释放内存。这个顺序错误在初学者代码里出现频率极高。为什么这里要传 ListNode* head因为有可能删除的恰好是头节点。比如链表是 [3, 1, 2]删除值为 3 的节点删完后头指针必须指向 1。如果函数参数不是引用函数内部更新了 head但 main 函数里的 head 还指向那个已经被释放的 3后续打印就乱套了。传引用后head dummy-next 会把新的头指针写回调用方。4.2 按位置删除节点配合题目操作的变体ACM 题里更常见的删除方式是按位置删除比如删除第 k 个节点。位置从 1 开始计数这就要求删除前先找到第 k 个节点的前驱。这里我直接用位置循环不用哨兵的话还得单独讨论 k1 的情况用了哨兵就统一了void deleteAtPosition(ListNode* head, int k) { if (k 0) return; ListNode* dummy new ListNode(0); dummy-next head; ListNode* prev dummy; for (int i 1; i k prev-next; i) { prev prev-next; } if (prev-next) { ListNode* target prev-next; prev-next target-next; delete target; } head dummy-next; delete dummy; }这里 for 循环的循环条件 i k prev-next 是个细节如果链表长度不够prev-next 会变成 nullptr循环提前结束最后 if (prev-next) 判断能防止对空指针解引用。有些题目保证 k 合法这个防御性判断就可以不加但为了函数健壮性我建议保留。4.3 释放整条链表deleteList 防止内存泄漏建链表用了多少次 new就要对应多少次 delete。释放整条链表的辅助函数长这样void deleteList(ListNode* head) { ListNode* cur head; while (cur) { ListNode* tmp cur; cur cur-next; delete tmp; } head nullptr; }这个函数的核心技巧是先保存 cur-next再删除 cur。因为 delete 之后 cur 的内存就释放了再去访问 cur-next 就是悬空指针。所以顺序必须是先取下一个节点地址存到 cur 里再 delete 当前节点。我习惯用一个临时变量 tmp 指向当前要删除的节点然后 cur 先推进最后 delete tmp这样语义更清楚。最后把 head 设为 nullptr 也很重要。这样调用方手里的指针变成空指针后续如果不小心又访问它至少是空指针的确定行为而不是漫无边际地乱访问一块已释放的内存。这类问题的坑在于已释放内存往往还能读出一部分数据程序可能看起来正常运行然后在下一次随机崩溃非常难查。5. 常见问题与排查技巧实录5.1 内存泄漏OJ 怎么 느려你ACM 本地测试小数据量时内存泄漏几乎无感因为总共就几千字节。但 OJ 的测试数据可能是成千上万组操作每组都泄漏一点累积到几十 MB程序就会被判内存超限MLE或者因为频繁分配导致运行变慢被判超时TLE。排查内存泄漏的办法在本地 Linux 环境可以用 valgrind命令很简单valgrind --leak-checkfull ./main。它会报告哪一行 new 的内存没有被 delete。Windows 下可以用 Visual Studio 的 CRT 调试工具或者干脆用 Dr. Memory。如果比赛环境不允许这些工具那就靠代码规范来保证每写一个 createList就配套写一个 deleteList主流程结束前必须调用。5.2 野指针与悬空指针访问已释放内存的经典现场野指针和悬空指针是链表题两大杀手。野指针是指针变量未初始化里面是随机地址悬空指针是指针曾指向一块内存但该内存已被释放。两种都会导致段错误或者随机崩溃。我用结构体构造函数让 next 初始化为 nullptr就是防野指针的第一道防线。防悬空指针的关键是在 delete 之后立刻做两件事要么把该指针设为 nullptr要么确保代码不会再次访问。上面 deleteNode 里我把 cur 指向 prev-next 而不是让 cur 保持原样就是这个目的。还有一个实操建议调试链表相关代码时写一个 printList 辅助函数把每个节点的地址和值都打印出来。一旦段错误你能看到崩溃前最后一个合法节点是谁基本就能定位问题。我平时排链表 bug 有一半靠这个函数。5.3 忘记更新头指针的半正确代码最坑的错误是看起来对实际错。比如删除头节点之后函数内更新了 head但因为参数不是引用调用者手里的头指针还是旧的。此时旧指针对应内存已被释放读它的 val 可能还是旧值打印可能依旧正常但访问它的 next 就不知道会跳到哪里。我排这种 bug 的体验是症状飘忽不定有时候输出正确有时候输出多加一个随机大数有时候直接崩溃。如果你在本地跑没事、一提交就错优先检查所有可能修改链表结构的函数参数是否用了引用。这个习惯帮我省了大量时间。5.4 常见问题速查表我把自己和身边同学踩过的坑整理成一张表写题前过一遍比掉进坑里再爬出来划算得多。症状可能原因排查与解决打印链表时多出一个 0哨兵节点没删除就返回返回前 delete dummy返回 dummy-next删除头节点后输出错乱函数参数未使用引用改为 ListNode* 传参随机段错误 / 崩溃访问已释放节点删除后置空指针或调整 delete 顺序内存超限MLE建表后未释放整条链表主流程结束前调用 deleteList输出顺序和预期相反用了头插法但以为是尾插法确认建表函数选择或用尾插法删除第 k 个节点时崩溃k 越界未加保护循环条件加 prev-next 判空6. 一个完整例题带你串起全部辅助函数6.1 B3631 单向链表题目要求与思路分析洛谷 B3631 是经典的单向链表练习题题面大致是初始有一个空链表接下来有 q 次操作操作类型分三种。第一种是在第 k 个插入的节点后面插入一个值为 x 的新节点第二种是删除第 k 个插入的节点第三种是查询第 k 个插入的节点的值并输出。这里的第 k 个插入是指按插入顺序编号每插入一个新节点它的编号就递增。这个题如果不做抽象直接第 k 个节点去写会在编号含义上绕晕。我的思路是把插入顺序编号和链表当前顺序位置分开处理。用辅助函数时插入操作对应在第 pos 个节点后插入删除操作对应删除第 pos 个节点查询对应取第 pos 个节点的值。这三个操作都可以基于我前面写的辅助函数扩展。核心是写一个 findNodeByPosition 函数返回第 pos 个节点的指针然后插入、删除、查询都围绕它展开。6.2 基于辅助函数的完整解法#include bits/stdc.h using namespace std; struct ListNode { int val; ListNode* next; ListNode(int x 0) : val(x), next(nullptr) {} }; ListNode* findNodeByPosition(ListNode* head, int pos) { ListNode* cur head; int cnt 1; while (cur cnt pos) { cur cur-next; cnt; } return cur; } ListNode* insertAfter(ListNode* head, int pos, int val) { ListNode* target findNodeByPosition(head, pos); if (!target) return head; ListNode* node new ListNode(val); node-next target-next; target-next node; return head; } ListNode* deleteAtPosition(ListNode* head, int pos) { if (pos 1) { ListNode* tmp head; head head-next; delete tmp; return head; } ListNode* prev findNodeByPosition(head, pos - 1); if (!prev || !prev-next) return head; ListNode* target prev-next; prev-next target-next; delete target; return head; } int main() { int q; cin q; vectorint inserted; ListNode* head nullptr; while (q--) { int op; cin op; if (op 1) { int k, x; cin k x; ListNode* target findNodeByPosition(head, k); ListNode* node new ListNode(x); if (!head) { head node; } else if (target) { node-next target-next; target-next node; } inserted.push_back(x); } else if (op 2) { int k; cin k; head deleteAtPosition(head, k); } else { int k; cin k; ListNode* target findNodeByPosition(head, k); if (target) cout target-val \n; } } deleteList(head); return 0; }这段代码里我保留了一个细节inserted 数组记录插入顺序主要用于编号逻辑的辅助理解实际操作仍然是对链表进行。这个题的难点在于删除操作会改变链表长度第 k 个插入的节点和第 k 个当前节点不是一回事。B3631 的设定是第 k 个插入的节点所以理想做法是给每个节点加一个 id 字段记录插入序号。如果要更严谨应该在 ListNode 里加 int id插入时赋值 id cnt删除和查询都按 id 匹配。我在上面的简版代码里用位置模拟适合理解辅助函数的用法真正提交时建议用带 id 的版本代码反而更简单。6.3 从辅助函数到常见链表变体建好一套创建、删除辅助函数后很多链表变体题都能复用。比如合并两个有序链表可以先写一个在尾部插入节点的内部小函数再用双指针遍历两条链逐个把较小节点接到结果链上。反转链表其实就是把原链表遍历一遍对每个节点头插到新链。环形链表判断则是快慢指针配合遍历辅助函数主要用于构造带环的测试数据。还有一类变体是循环单链表。尾节点的 next 指向头节点创建函数里尾插完成之后要把 tail-next 指回头节点。删除操作路径就会更复杂循环结束条件要从 cur nullptr 变成 cur 头节点。这里我更推荐在辅助函数内部仍然维护一个哨兵节点能显著降低边界的复杂度。另外提一句有些读者用 Python 刷题Python 里链表节点一般写成类创建、删除不需要手动管理内存但逻辑结构完全一样。你仍然需要单独写 createList 和 deleteNode 之类的函数只是 delete 变成了让垃圾回收器去处理代码里更多的是断链操作。原理是通用的照着 C 的思路平移过去即可。7. 最后聊几句个人习惯我写链表题大概经历了三个阶段第一阶段每次都在 main 里临时拼遇到删除头节点就 panic第二阶段把辅助函数单独封装错误率明显下降第三阶段开始追求一次把模板写到能直接复用包括创建、删除、查找、打印这四大件。这个模板我用了好几年靠它平稳度过了机试和若干场比赛。如果你也在积累自己的代码模板真的建议把链表辅助函数当成第一块积木来打磨因为链表是递归、树、图这些数据结构的底层基础这里理顺了后面很多题都会顺畅很多。