刷链表刷到 Day3整个人已经进入一种“看见 next 就条件反射画箭头”的状态。今天这三道题——203.移除链表元素、707.设计链表、206.反转链表放在一起刷完你会发现链表题翻来覆去就考那几件事怎么安全地改 next 指向、怎么处理头尾两个特殊位置、怎么在遍历过程中不把链表走断。这三题分别是“删除节点”“设计完整链表结构”“翻转指针”三个方向的典型代表也是很多训练营都会安排在同一天完成的“链表基本功三件套”。如果你刚开始刷链表、写指针经常乱或者之前已经在 707 这种全操作题上交过学费那这篇文章就是给你准备的。我会把每道题的思路、代码、容易翻车的细节都过一遍最后再总结一套能用在所有链表题上的通用排查方法保证你看完能直接上手写而不是只会对着题解点头。1. 为什么把三道题放一起练链表题的三个基本功1.1 链表的本质和唯一的难点链表在结构上其实特别简单每个节点就是一个“值 指针”的组合。用 C 描述就是struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };你可以把它理解成一条寻宝线索你只知道第一张纸条放在哪里每张纸条上写着“下一个纸条的位置”想找到第五张纸条就必须从第一张开始顺着 next 一个一个走过去。数组可以靠下标直接跳到任意位置链表不行这是它最“笨”的地方也是它所有题目的出发点你只能在遍历的过程中改东西而且改的时候还不能把还没走的路线弄丢。链表题翻来覆去就是这三个难点第一怎么在遍历时同时维护“当前节点”和“前一个节点”第二怎么处理头节点和尾节点这两个没有完整前后关系的特殊位置第三怎么在修改 next 指向的时候先把原来的 next 保存下来防止断链。很多新手觉得链表题难其实不是语法不会而是这三个问题没拆开想清楚。1.2 三道题分别命中哪类考点203.移除链表元素考的是最基础的删除动作。删除的本质不是“删掉自己”而是让前一个节点的 next 跳过自己、指向自己的下一个节点。这里立刻就会碰到一个麻烦如果要删的是头节点那它没有前驱怎么跳于是引出了虚拟头节点这个经典解法。把 203 吃透后面所有和删除有关的题都能少踩一半坑。707.设计链表直接要求你实现一个完整的链表类里面有头插、尾插、任意位置插入、删除、按下标取值。这题已经不是在考“某一步怎么改指针”而是考“一堆方法放在一起时索引合法区间怎么判断、边界条件怎么统一”。很多人在单道题里能写出正确的删除逻辑但一放到设计题里就顾此失彼因为五个方法共用同一套成员变量一个地方写错别的操作也被带崩。206.反转链表考的是连续修改 next 的能力。反转意味着每一轮循环都要改一个节点的指向而且改了之后你还要能继续往后走这就必须提前保存原来的 next。这是链表题里最容易出现死循环和断链的一类也是面试最高频的基础题之一值得单独拿出来反复练。1.3 比较推荐的刷题顺序我个人建议按照 203 → 707 → 206 的顺序来。203 先让你熟悉“遍历 删除 定位前驱”的节奏代码量最小心态不容易崩。707 再逼你把增删查三个动作分别写一遍此时你会发现之前 203 里那个“删除当前节点”的逻辑其实就是 707 里 deleteAtIndex 的核心。最后到 206你已经知道怎么安全地遍历链表再学怎么安全地换向会比一上来就硬啃反转轻松很多。这个顺序也符合人的认知习惯先把一个动作练标准再同时做多个动作最后做高难度的连续动作。如果跳着刷很容易卡在“指针绕不过来”上一卡就容易放弃。2. 203. 移除链表元素虚拟头节点能省掉一半脑力2.1 题意拆解与删除逻辑题目要求把链表中所有值等于 target 的节点都删掉。注意“所有”这两个字不是删第一个就完事而是从头走到尾见一个删一个。最直接的思路是遍历链表用一个 cur 指针表示“当前正在检查的节点的前一个节点”如果 cur-next 的值等于 target就把 cur-next 从链表中拆下来。这里有一个绕不开的问题头节点本身也可能等于 target。如果 head 的值就是要删的值它没有前驱节点你的 cur 指针从 head 开始就没法操作。两个解决办法要么单独写一个 while 循环先处理头部要么造一个虚拟头节点让所有删除逻辑统一。后者代码更干净也更能体现链表操作的精髓所以我强烈推荐先在草稿纸上把虚拟头节点这个方案画明白。2.2 直接处理头部 vs 虚拟头节点先看不用虚拟头节点时要怎么写。核心就是先把头部连续等于 target 的节点删掉然后再处理后面class Solution { public: ListNode* removeElements(ListNode* head, int val) { // 先处理头节点连续等于 val 的情况 while (head ! nullptr head-val val) { ListNode* tmp head; head head-next; delete tmp; } // 再处理中间节点 ListNode* cur head; while (cur ! nullptr cur-next ! nullptr) { if (cur-next-val val) { ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; } else { cur cur-next; } } return head; } };这种写法也算直观但你要处理两种完全不同的情况头节点是一套逻辑非头节点是另一套。人脑在写代码时分支越多就越容易漏尤其是“如果链表一开始全是等于 val 的节点删到 head 变成 nullptr后面的循环还能不能跑”这种边界很容易想岔。再看虚拟头节点版本class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* dummy new ListNode(0, head); // 虚拟头节点next 指向真正的头 ListNode* cur dummy; while (cur-next ! nullptr) { if (cur-next-val val) { ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; } else { cur cur-next; } } ListNode* newHead dummy-next; delete dummy; return newHead; } };看到区别了吗用了 dummy 之后循环里永远是在处理“cur-next 这个节点”头节点和普通节点没有任何区别因为 dummy 就是头节点的“前驱”。你不再需要单独写一段 while 去清理头部所有等于 val 的节点都被同一条规则处理。很多刷题老手都会默认用虚拟头节点不是因为它能提升性能它反而多分配了一个节点而是因为它能把逻辑复杂度降下来人不容易出错。2.3 这道题容易翻车的三个细节第一个细节是连续相同值节点的删除。假设链表是 1 → 2 → 2 → 2 → 3要删 2。你第一次发现 cur-next 是 2把 cur-next 改成下一个 2此时 cur 不要移动因为新的 cur-next 还是 2需要继续判断如果你在删除后顺手让 cur cur-next就会漏删。代码里的 else 分支保证只有“当前节点不用删”时才前进这个细节看着小写错的人非常多。第二个细节是遍历条件。循环条件是while (cur-next ! nullptr)不是while (cur ! nullptr)。因为循环体里要访问 cur-next-val如果 cur-next 已经是空指针访问就会崩溃。这个条件隐含的意思是“cur 是安全的前驱”cur 本身永远不是空指针因为它是从 dummy 开始的而 dummy 不会被删。第三个细节是内存释放。刷题的时候很多人直接cur-next cur-next-next不 deleteOJ 一般也不会报错因为整个程序内存由系统回收。但面试时如果被问到内存泄漏最好还是用 tmp 先保存要删的节点再 delete既能体现工程意识也符合“谁 new 谁 delete”的习惯。要注意 delete 之后不能再访问 tmp-next所以一定要先把 cur-next 更新完再 delete tmp顺序反了就是悬空指针。3. 707. 设计链表一个类的增删改查把边界问题一次性补齐3.1 题目要求与整体思路这题要求自己实现一个 MyLinkedList 类包含 get、addAtHead、addAtTail、addAtIndex、deleteAtIndex 五个方法。看起来不难但它是所有链表题里“工程味”最重的一道因为你要同时考虑索引合法性、指针连接顺序、size 的维护五个方法还会互相影响。写这题的时候最容易出现的状态是单个方法单独看都能看懂放在一起编译运行就崩。我的建议是定义两个成员变量一个虚拟头节点dummy一个长度size。dummy的作用和 203 里一样统一所有对头部的操作size的作用是让 get、addAtIndex、deleteAtIndex 能立刻判断索引是否合法而不是每次遍历链表数长度。这里要提前做一个设计决策dummy 节点本身不存储有效数据下标 0 对应的是 dummy-next下标 size-1 对应最后一个有效节点。明确这一点后面所有遍历的步数都不会错。3.2 完整代码实现class MyLinkedList { private: struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* dummy; int size; public: MyLinkedList() { dummy new ListNode(0); // 虚拟头节点不存数据 size 0; } int get(int index) { if (index 0 || index size) return -1; ListNode* cur dummy-next; // 第一个有效节点 for (int i 0; i index; i) { cur cur-next; } return cur-val; } void addAtHead(int val) { ListNode* node new ListNode(val); node-next dummy-next; dummy-next node; size; } void addAtTail(int val) { ListNode* cur dummy; while (cur-next ! nullptr) { cur cur-next; } cur-next new ListNode(val); size; } void addAtIndex(int index, int val) { if (index size) return; // 大于长度不插入 if (index 0) index 0; // 负数按 0 处理即头插 ListNode* cur dummy; // 从虚拟头开始走 for (int i 0; i index; i) { cur cur-next; } ListNode* node new ListNode(val); node-next cur-next; cur-next node; size; } void deleteAtIndex(int index) { if (index 0 || index size) return; ListNode* cur dummy; for (int i 0; i index; i) { cur cur-next; } ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; --size; } };这个版本的核心思路是所有需要定位的操作都从 dummy 出发走 index 步到达“目标位置的前一个节点”。get 比较特殊它要取第 index 个节点的值所以从 dummy-next 开始走 index 步。addAtIndex 和 deleteAtIndex 要改的是前驱的 next所以从 dummy 开始走 index 步。这几种遍历的起点不同、步数不同是这题最容易混的地方我下面详细展开。3.3 关键的边界规则速查方法index 合法范围说明get[0, size - 1]越界返回 -1addAtIndexindex 0 按 0 处理index size 允许等于 size 时做尾插大于 size 不插入deleteAtIndex[0, size - 1]等于 size 时没有可删节点直接返回很多人会问为什么 addAtIndex 允许 index 等于 sizedeleteAtIndex 却不允许因为插入操作是“在某个位置前面插入一个新节点”当 index 等于 size 时插入位置是最后一个有效节点之后、nullptr 之前这恰好等价于 addAtTail而删除操作必须有一个真实存在的节点让你删size 位置并不存在节点所以不合法。这类边界规则光靠背不够最好自己在草稿纸上画一画长度为 2 的链表分别把 index2 代入 add 和 delete 试一遍。3.4 这题最容易写错的三个位置第一个是遍历步数的 for 循环。addAtIndex 里for (int i 0; i index; i)不是 index。因为 dummy 在逻辑上是“下标 -1 的节点”走一步到下标 0 的前驱走 index 步正好到下标 index-1也就是插入位置的前驱。如果写成 index你会走到下标 index 的位置插入点会比预期靠后一个节点最后链表的顺序全是错的而且越界时还会访问空指针。第二个是插入时的接线顺序。一定要先让新节点的 next 指向cur-next再让cur-next指向新节点。如果先把cur-next指向新节点原来的后半段链表就丢了因为没有任何变量再保存它新节点后面接的只能是自己或者空指针链表直接断裂。这个错误在 addAtHead 里也容易犯本质都一样。第三个是删除时的 tmp 保存。deleteAtIndex里如果没有ListNode* tmp cur-next;直接cur-next cur-next-next;然后 delete你会发现 delete 之后cur-next指向的已经不是原来的下一个节点因为原来的节点已经被释放了。delete 前保存 tmpdelete 后 tmp 不能再碰只把它当成一个“已经被摘下来”的孤儿节点就好。写完 707 之后你会特别深刻地感觉到链表操作不怕逻辑难就怕边界多。一个 size 变量贯穿五个方法任何一个方法忘记更新 size后面所有判断都会连锁出错。头插和尾插之后 size删除之后 --size这个动作要形成肌肉记忆。4. 206. 反转链表三指针换向与递归的两种理解方式4.1 反转的本质反转链表就是把每个节点的 next 从“指向后一个”改成“指向前一个”。从头节点开始依次处理最后原来的尾节点变成新头。这题为什么经典因为它考察的是一种“在破坏原先连接关系的同时仍然能继续前进”的能力。链表和数组最大的不同就是你改了一个节点的指向可能会让后面所有节点访问不到必须提前把后路保存下来。反转前的链表虽然是单向的但它隐含着一层“下一个节点在哪”的信息而这层信息恰恰在你修改 next 的瞬间就消失了。所以反转的每一步都像拆炸弹动手改线之前先确认还有没有另一根线能拉到下一站。4.2 迭代法pre、cur、temp 的铁三角迭代法需要三个指针pre 表示“已经反转好的部分的新头”初始是 nullptrcur 表示“当前正在处理的节点”初始是 headtemp 用来保存 cur-next防止改完指向后找不到后续节点。每一轮的步骤固定temp cur-next先把后路记下来cur-next pre把当前节点掉头指向已反转部分pre cur当前节点归入已反转部分pre 前进到 curcur temp继续处理原来的下一个节点。用链表 1 → 2 → 3 → 4 → nullptr 走一遍轮次操作前 pre操作前 curtemp 保存操作后 pre操作后 cur链表状态1nullptr1212nullptr ← 12 → 3 → 4212323nullptr ← 1 ← 23 → 4323434nullptr ← 1 ← 2 ← 34434nullptr4nullptrnullptr ← 1 ← 2 ← 3 ← 4循环结束的条件是 cur 变成 nullptr此时 pre 正好停在原链表最后一个节点上也就是反转后的新头所以函数返回 pre。这个返回值是很多人会错的点循环结束时 cur 已经是空指针你要是顺手 return cur那返回的就是个空链表。迭代版代码class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* pre nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* temp cur-next; // 保存后路 cur-next pre; // 反转指向 pre cur; // pre 前进 cur temp; // cur 前进 } return pre; } };4.3 递归法把“反转后面的部分”当成一个黑盒递归版的思路和迭代完全不一样。假设链表是 1 → 2 → 3 → 4 → nullptr我们先不管 1而是递归反转后面的 2 → 3 → 4反转完得到的新链表是 4 → 3 → 2。此时 2 这个节点变成了新链表的尾节点而且 2 的 next 是 nullptr。接下来要做的就是让 2 重新指向 1也就是执行head-next-next head再让 1 的 next 置空防止成环。代码写出来很短但理解上需要一个跳变class Solution { public: ListNode* reverseList(ListNode* head) { if (head nullptr || head-next nullptr) return head; ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; } };递归结束条件为什么是“head 为空或 head-next 为空”因为当链表只有一个节点时它反转后还是自己不需要继续递归当链表为空时返回空即可。很多初学者会漏掉head-next nullptr这个条件导致递归到最后一个节点时head-next已经是 nullptr再调用reverseList(nullptr)栈一直压到爆。递归版最反直觉的地方在于你需要相信reverseList(head-next)已经帮我们把后半段反转好了不要一步一步去跟着栈想否则会越想越乱。你只需要站在head的视角处理两件事把后一个节点的 next 指回自己同时把自己的 next 断掉。至于后半段内部怎么反转的黑盒已经处理好了。head-next nullptr这一步尤其重要如果省略原链表第一个节点仍然指着第二个节点而第二个节点反转后又指着第一个节点两个节点会形成一个环遍历的时候永远走不到头。4.4 反转题常见的三个现场翻车点第一种是没保存 temp 直接改指向。四个步骤少一个都不行少了 temp 保存cur temp就成了cur 悬空指针程序直接崩溃。第二种是更新顺序写反比如先cur cur-next再去改 cur-next 的指向实际上你改的已经是后一个节点的 next 了原节点根本没被反转。第三种是递归版忘记断尾形成环。排查方法很简单如果反转后输出链表时程序死循环或内存爆掉十有八九是某个节点的 next 指回了它前面的节点。Python 写迭代反转时有人喜欢用多变量赋值一笔带过比如cur.next, pre, cur pre, cur, cur.next这个写法虽然简洁但初学者容易忽略右边在赋值前已经按原值计算好了本质上还是四步操作。我个人建议刚学的时候先老老实实写四行等完全熟练了再追求一行赋值否则出错时根本不知道是哪个指针被提前覆盖了。5. 三道题一起复盘链表通用方法论与速查表5.1 画图是最高效的 debug 方式刷完这三道题我最大的体会是任何指针题先在纸上画图都能把正确率提高一半。不需要画得多精致就画几个方框代表节点方框之间画箭头代表 next然后用不同颜色的笔标注 pre、cur、temp 分别指向谁。每执行一步操作就擦掉旧箭头、画上新箭头。我在写反转链表前