算法竞赛里提到链表很多人第一反应是手写单链表、指针满天飞而一说到 list又会开始纠结“STL 里明明有现成的 list为什么我还要自己写”这个问题我自己当年也问了很久最后是在一场题里被虐了之后才想明白的。链表并不是一个“必须绕开”的数据结构但也不是一个“多用就高级”的数据结构。它的适用范围、代码写法、甚至“要不要用”在不同的比赛场景里差得非常远。这篇文章的内容是我把链表和 std::list 放在竞赛语境下重新梳理了一遍包括最基础的单链表操作、静态链表为什么是竞赛中的主流、std::list 到底有哪些值得用的接口以及我自己在实际做题时踩过的那些断链、迭代器失效、排序翻车的大坑。如果你正准备算法竞赛或者正在刷“链表”相关题目希望这篇文章能帮你省下一些走弯路的时间。1. 先从数组的痛讲起链表到底解决了什么问题很多初学者学链表时都会有一种感觉明明数组用得好好的为什么要引入一个这么容易断链的东西这个疑问非常正常因为链表的价值不是“让代码看起来复杂”而是解决数组在特定操作上的结构性问题。数组和 vector 之所以快是因为内存连续随机访问任意下标的元素都是 O(1)而且连续内存对 CPU 的缓存非常友好。问题是如果你需要在数组的中间插入或删除一个元素后面的所有元素都得整体往后挪一格或者往前挪一格单次操作最坏是 O(n)。在数据规模达到十万、百万级还要反复进行中间插入删除时这种搬移成本会迅速变成程序的主要瓶颈。链表解决的就是这个痛点。它把每个节点独立存放节点之间用指针串联逻辑上相邻的两个元素在物理内存里可以隔得很远。只要你能拿到某个节点的位置在它后面插入一个新节点或者删掉它的后继节点都只需要改写少量指针时间复杂度稳定在 O(1)。那链表是不是什么都比数组好也不是。它随机访问一个元素时必须从头指针开始一个一个往后走复杂度 O(n)节点之间靠指针跳跃缓存命中率通常不如连续数组每个节点还要额外地存储一个或两个指针内存开销更大。所以我们可以先把结论放在这里链表是“局部高效”的数据结构它只擅长中间插入和删除除此以外的大部分场景数组才是更合理的默认选择。在算法竞赛里链表的典型价值体现在几个方向约瑟夫环这类需要反复删除某个位置元素的模拟题合并多个有序链表维护一个有序结构某些图中用“链式前向星”存边本质上就是静态链表需要“把某个节点摘下来再插到另一个地方”这类复杂指针操作。这些场景的共同特征是操作位置已知而不是需要通过下标随机访问。理解了这一点再去写链表、选 list思路会清晰很多。2. 手写单链表从节点定义到核心操作的每一处细节手写链表是理解链表机制逃不开的一步。就算你以后在赛场上不用指针链表这些操作背后的“断链”思路也会在静态链表和 std::list 的使用中反复出现。2.1 节点结构最基础的定义单链表节点最简单的定义方式是这样的struct Node { int val; Node* next; Node(int x) : val(x), next(nullptr) {} };这一步很简单但很多新手在这里第一个问题就来了要不要写构造函数我的建议是写一个带参构造因为竞赛里经常会用new Node(x)快速创建节点。如果不写构造函数每次都得Node* node new Node; node-val x; node-next nullptr;代码量大还容易漏初始化。另外经常会听到“带头结点”和“不带头结点”两种说法。这里的头结点不是第一个存储数据的节点而是一个不存业务数据的哑节点dummy node它的 next 才指向真正的第一个元素。带头结点的好处是不管链表为空还是非空插入、删除操作都只需要处理统一的逻辑不需要对头指针本身做特殊判断。不带头结点的写法更省一个节点但头部插入时必须想办法修改头指针本身。2.2 插入操作头部、尾部和指定位置不带头结点的头部插入核心是更新头指针。我早期经常写错void insertHead(Node* head, int x) { Node* node new Node(x); node-next head; head node; }注意这里必须用Node* head或者把新的头指针作为返回值传出去。用Node* head传参的人往往在函数内部修改了 head出函数后原链表一点变化都没有原因就是指针本身也是按值传递的。尾部插入稍微麻烦一点因为需要先找到尾节点。如果链表没有维护 tail 指针就得遍历一遍复杂度 O(n)。还有一个小细节找到尾巴后tail-next node;记得把新节点的 next 初始化为 nullptr尤其当你用自定义 struct 而不写构造函数时。指定位置插入最常见的是“在第 p 个节点后面插入一个新节点”。操作顺序非常关键Node* node new Node(x); node-next p-next; p-next node;先让新节点链上 p 原来的后继再把 p 的 next 指向新节点。这两句话顺序反了后面的节点就丢了。很多人刚开始写链表犯的第一个“断链”错误就是这里。2.3 删除与遍历先保住后面的节点删除一个已知节点时单链表必须拿到它的前驱 prev因为我们要通过 prev 跳过被删除节点。别直接 delete 完再用指针已经悬空了。正确的删除逻辑Node* temp prev-next; prev-next temp-next; delete temp;先把待删除节点temp保存下来再让前驱的 next 指向 temp 的下一个最后释放 temp。这里有一个通用原则在改指针之前先把所有还要用的指针保存下来。这句话能避免 80% 的断链问题。如果删除的是头结点需要额外更新 head如果链表只有一个节点还要考虑 head 变成 nullptr。所以我在实际做题时更推荐带头结点或者在操作处加一个 dummy 节点这样边界处理会简单很多。2.4 反转链表迭代和递归都要会链表反转是面试题和算法题里出现频率极高的操作。迭代版的思路是三个指针prev、cur、next。每次把 cur 的 next 指向 prev三个指针整体往后移动。Node* reverseList(Node* head) { Node* prev nullptr; Node* cur head; while (cur ! nullptr) { Node* next cur-next; cur-next prev; prev cur; cur next; } return prev; }这里需要注意cur-next一旦改掉原本的后续节点就找不到了所以一定要在改指针前用next保存。很多人写的反转代码死循环或者链表断裂基本都是没保存这一步。递归反转考的是对递归栈的理解。假设newHead reverseList(head-next)已经把后面一串反转好了那么当前这个节点要做的事就是让head-next-next head再把head-next nullptr断开防止成环。递归写起来很短但思考成本略高不适合在紧张比赛中现推最好是提前背熟一个版本。2.5 数组模拟链表静态链表竞赛里真正的主流指针链表在教学中很好用但到了算法竞赛里面用new Node(...)一个一个创建节点常常会触发性能问题Node 数量大时内存分配的耗时很可观而且频繁 new/delete 会让内存碎片化。更重要的是指针链表没法用简单下标去调试稍微复杂一点肉眼根本看不出指针指向了什么。所以竞赛圈更常见的做法是静态链表。所谓静态链表就是用数组来模拟节点的存储和指针关系。常见写法是const int MAXN 100000 5; int e[MAXN], ne[MAXN], head -1, idx 0; void addToHead(int x) { e[idx] x; ne[idx] head; head idx; } void addAfter(int pos, int x) { e[idx] x; ne[idx] ne[pos]; ne[pos] idx; } void removeAfter(int pos) { ne[pos] ne[ne[pos]]; }这里的idx相当于分配新节点的指针每次插入就申请一个下标ne数组存的是下一个节点的下标head存的是头节点下标。和指针链表相比静态链表的特点是没有new/delete内存分配几乎零成本所有节点都存放在数组里内存是连续申请的虽然没有像 vector 那样的强局部性但好在可控调试时可以打印e[0...idx-1]查看节点内容也可以直接打印ne数组观察链接关系。很多图论里的链式前向星本质上就是多组静态链表。把 head、next 换成带头节点数组的边表就形成了常见的邻接表实现。学会静态链表不只对“链表题”有用对图论存图也直接有用。3. std::list 的接口和运行机制竞赛里如何用对既然手写链表这么麻烦那直接用 STL 的 std::list 不就行了也不是不行关键是你得先搞清楚 std::list 到底是什么以及它的哪些接口在竞赛里真正有价值。3.1 list 是双向链表迭代器比手写单链表更稳定std::list 是标准库实现的双向链表。和前面手写的单链表相比它最大的区别是每个节点都保存了 prev 和 next 两个指针所以它支持双向遍历可以在 O(1) 时间内往当前迭代器位置的前面或后面插入元素。更好的一点是std::list 的迭代器稳定性比其他容器高。你在 list 中插入或删除元素不会导致容器里其他元素的迭代器失效只有指向被删除节点的那个迭代器会失效。对比 vector 在中间插入可能导致整个容器的迭代器全部失效list 在需要长期保存某个位置的场景里会很有优势。但代价也很明显每个节点多了一个指针内存占用更大迭代器只能自增自减不能直接做it 5也没法把它传给 std::sort 这类需要随机访问迭代器的算法。3.2 值得掌握的成员接口splice、merge、remove、uniquestd::list 好多接口是 vector 没有的其中最值得记的是 splice。它可以把你指定的一个或一段节点从另一个 list 中直接拼接过来复杂度是 O(1)。这个接口在实现某些模拟题时非常方便——比如从 A 链表里摘一个元素放到 B 链表的指定位置不需要先插入再删除splice 一步完成。我们可以把 list::splice 可以理解为“CtrlX 再 CtrlV”它操作的是节点本身而不是拷贝节点数据。举个例子std::listint a {1, 2, 3}; std::listint b {4, 5, 6}; auto it a.begin(); std::advance(it, 1); // 指向2 a.splice(it, b); // 把 b 全部拼到 a 中 it 位置之前 // a: 1 4 5 6 2 3b 变为空merge 同样是单向的归并操作。要求两个 list 都是有序的复杂度和归并排序一样是 O(n)。remove 按值删除所有匹配元素unique 把相邻重复元素压缩成一个。这些都封装好了写题时如果场景刚好匹配能省不少事。3.3 list 排序的“坑”不能直接用 std::sortstd::list 麻烦的地方在于排序。因为 std::sort 是要求随机访问迭代器的而 list 的迭代器是双向迭代器不满足要求。所以你不能写sort(myList.begin(), myList.end()); // 编译错误得用它的成员函数myList.sort();list::sort 自己实现的是归并排序并且是稳定排序。这在需要稳定性的题目里反而是个优点。不过它的常数比较大节点分散导致缓存不友好所以数据量大的时候规范做法往往是先把 list 转成 vector 或拷到数组里排序再重组链表。这在竞赛里很常见list 负责维护结构数组负责排序。不要有“用了 list 就必须全程 list”的执念。3.4 小心Python 的 list 不是链表如果你的“链表 list”话题指的是 Python那么这里必须强调一个经典误区Python 内置的 list 是动态数组不是链表。它底层是连续内存、支持随机访问在中间插入删除同样是 O(n)只是由 Python 解释器帮你完成了内存管理。所以用 Python 刷算法题时如果你想要链表得自己定义 Node 类或者使用 collections.deque 来模拟部分双端队列的功能但 deque 也不是传统链表它是分块存储的双端队列。很多 Python 选手在刷“LRU 缓存”或“约瑟夫环”时把 list 当成链表用结果复杂度完全不是预想的那样很容易超时。4. 链表题型的套路拆解从真题看考点链表在算法竞赛中的题型相对固定不能算多但套路感很强。下面这几个方向是我认为最值得反复打磨的。4.1 约瑟夫环链表模拟与数学递推的取舍约瑟夫环大概是链表模拟最经典的题目。问题描述很简单n 个人围成一圈每数到 m 就淘汰一个人问最后的幸存者下标。用链表模拟最直观构造一个循环链表每次绕圈走 m 步摘掉当前节点直到剩下一个节点。这里的“摘掉”操作正好考验链表 delete 的能力。如果直接用 std::list配合 erase 也能做但要注意 erase 返回的迭代器别让它失效。不过竞赛里真正的正解往往是数学递推O(n) 就能算出来不需要链表模拟。为什么还要练链表版本因为约瑟夫环的链表法思维简单适合作为链表操作的“组合拳”练习。如果题目数据范围很大比如 n1e7m 也很大的时候链表模拟显然不够用必须上数学递推。这时候能不能画出递归公式比会不会写链表更重要。4.2 快慢指针中点、环检测、相交链表题的另一个大套路是快慢指针。慢指针每次走一步快指针每次走两步。利用这个速度差可以做到找链表中间节点快指针到末尾时慢指针刚好在中点判断链表是否有环快慢指针最终会相遇找环的入口相遇后让一个指针从头出发另一个从相遇点出发每次走一步再次相遇的位置就是环入口找倒数第 k 个节点快指针先走 k 步然后两个指针同步走。快慢指针的思想很简单但实现时容易忽略一个问题链表节点总数奇偶不同快指针对空的判定条件要写对。一般写成while (fast ! nullptr fast-next ! nullptr)否则 fast 可能先走到空导致解引用空指针。这些边界条件调试起来比插入删除更隐蔽。4.3 反转与逆置的变体K 个一组翻转“逆置链表”是热搜词里出现很多的点基础版是整条链表反转进阶版是每隔 K 个节点反转一组。后者的代码量不小但它其实是“找区块 反转子链 重新拼接”的组合题。K 个一组翻转的难点在于每次翻转一个子区间后要把子区间的前后都接好。我自己的习惯是引入 dummy 节点作为哨兵然后维护四个指针pre当前子区间前一个节点、start子区间起点、end子区间终点、nextGroup下一个子区间入口。每次先通过循环找到 end然后写一个单独的反转函数将 [start, end] 区间翻转返回新的头和尾再把它接回 pre 后面。这个题不要现场硬推最好是背一个自己觉得容易写的模板。我比赛时如果时间紧张宁可用 vector 存下节点指针翻转完再串起来——时间复杂度 O(n)空间复杂度 O(n)虽然理论上不是最优但比现场写错强一万倍。4.4 链表的归并、合并与排序两路有序链表合并是入门题多路有序链表合并则可以配合优先队列做。链表归并排序需要先找中点再递归排序左右两半最后合并。由于链表是离散存储的归并排序不像数组那样需要额外 O(n) 辅助空间这算是链表题里少有的“比数组更轻”的场景。比赛里的通用技巧是先遍历一遍链表把节点指针存进 vector然后对 vector 排序或翻转最后重新设置 next。对于非核心考点的题目这一招非常稳虽然损失了一点空间但能大幅降低出错率。个人看法是除非题目明确考察链表操作否则没有必要为了“纯链表解法”而硬撑。5. 选型决策指针链表、std::list、静态链表到底用哪个很多人学了链表以后拿到题目就纠结“要不要用链表”。我的建议很简单先看题目让你维护的数据结构是什么样的操作模式再看内存和时限约束最后决定用哪种实现。下面这张表是我日常做题时的参考思路数据结构中间插入/删除随机访问局部性内存开销什么时候用vector/数组O(n)O(1)很好小大多数场景默认选择静态链表O(1)O(n)中较小图论存边、需要高密度节点分配std::listO(1)O(n)差大迭代器稳定、splice 拼节点手写指针链表O(1)O(n)差中教学练习、特殊内存控制这张表背后有一个容易被忽略的重点时间复杂度不是唯一指标。现代 CPU 上vector 的中部插入虽然理论是 O(n)但如果 n 只有几千或者插入次数不多它可能比 list 更快因为连续内存的缓存命中率太好了。相反std::list 每个节点都要动态分配内存可能在 new/delete 上就花掉很多时间。竞赛环境下我见过太多“用了 list 结果超时”的选手把代码改成静态链表后立刻 AC。所以我自己的决策顺序是能不手工管理节点就别手工管理优先 vector需要保持节点顺序且频繁中间插入但数据量有限可以用 std::list需要高性能且要模仿链表逻辑用静态链表只有题目明确考指针操作或者内存需要手动管理才去写手写指针链表。如果你参加的是 ICPC/CCPC 这种对常数极其敏感的比赛这条决策顺序应该反过来一部分静态链表的优先级会比 std::list 更高。因为 list 的封装虽然方便但它的节点内存池不一定和你的题目数据规模匹配反复申请释放带来的开销是真实存在的。6. 我踩过的链表大坑最后这部分我想分享几个自己实际踩过、且有代表性的坑。它们不是知识点本身但比知识点更影响比赛体验。6.1 断链的根源改指针之前没保存后路十次链表 debug八次发生在我把next指针改了以后又回头找原来的节点。比如删除节点时有些人喜欢先delete p;再执行prev-next p-next;这等于把已经释放的内存又读了一遍。竞赛里虽然经常不会立刻崩溃但结果是不可预测的。根治方法很土但很有效任何修改 next 的操作优先把原来的 next 保存到一个局部变量里。写反转、插入、删除时先画出这个小图再动手写代码。我见过很多高手也不是不犯这个错只是他们用模板把常见操作固定下来了。6.2 迭代器失效erase 之后别再用旧迭代器用 std::list 做题时erase 之后旧迭代器就失效了。很多人会写类似下面的代码for (auto it lst.begin(); it ! lst.end(); it) { if (*it val) lst.erase(it); }这是典型错误erase 后 it 已经失效再 it 属于未定义行为。正确做法是使用 erase 的返回值或者先保存 next 迭代器for (auto it lst.begin(); it ! lst.end();) { if (*it val) it lst.erase(it); else it; }这个坑在 vector 里也存在但 list 的 erase 语义容易让人放松警惕因为 total 的迭代器稳定。记住一句话稳定的是别的迭代器不是被删的那个。6.3 list::size 和 splice 的复杂度疑云还有一个容易被忽视的点是 list::size 的复杂度。现代 C 标准要求标准容器的 size() 是常数复杂度但一些旧编译器的 list::size() 实现是 O(n)它要遍历节点计数。如果你在比赛环境中用老编译器或者不确定实现就不要在循环里反复调 size()。同样的道理splice 在给定迭代器时是 O(1)但如果只给一个指向 list 的迭代器而不指定来源迭代器某些重载同样能 O(1) 完成。不过要注意 splice 会“摘走”别的 list 的节点如果你在遍历一个 list 的同时 splice 另一个要小心别把迭代器搞混。我自己的习惯是splice 前后都打印一下两个 list 的长度确认预期。6.4 调试技巧打印链表、白板验证、防御性断言链表变长了以后人肉跟踪指针几乎不可能。我的建议是写一个简短的打印函数专门输出从 head 开始的所有节点值每走一步都在纸上或注释里画一下预期状态。对于重灾区操作比如反转和 K 个一组翻转我还会加断言// 反转后必须保持节点个数不变 assert(sizeOfList(newHead) sizeOfList(oldHead));这种断言不能帮你直接找到断链点但能在第一时间告诉你“操作前后链表长度不一致”快速缩小问题范围。比赛时担心 assert 影响性能可以在本地调试打开提交前注释掉。最后再分享一个我的个人习惯赛前会准备一份静态链表的基本操作模板包括头插、尾插、按值查找、删除指定下标、遍历打印、反转。这份模板不用多能覆盖 90% 的“链表应用”题就够。真正遇到需要 std::list 的题我反而会现场查接口确认。因为 list 的接口不像 vector 那么常用背错 splice 的签名比不会写链表还难受。链表这个东西你看别人写觉得很简单自己写几遍才发现细节全在“断链”和“边界”里。但只要你能顺手写出静态链表又能说清楚 std::list 的适用场景竞赛里绝大多数和链表相关的题目就都拦不住你了。