说实话第三天这份题单我原以为会是轻松的一天。毕竟 203、707、206 这三道题听起来就像链表操作的入门三板斧。结果整个下午基本都耗在“指针到底指哪去了”这种问题上尤其是 707 设计链表六个方法写下来边界条件多得让人头皮发麻。如果你也在刷算法训练营或者刚开始啃链表这篇文章就是按我踩坑的路线整理的每个题背后的核心难点、为什么那样写、以及我实测下来最容易翻车的地方。本文适合这几类人第一次接触虚拟头节点的人写 707 时不知道如何组织增删逻辑的人反转链表画不出图、只能靠背代码的人。看完你应该能收获一份可以直接复用的链表操作心法而不是一堆死记硬背的答案。1. 为什么刷了三道链表题感觉像重新学了一遍数据结构1.1 我这几天的真实状态我在数组那几天的状态还算舒服因为数组的一切操作都可以靠“下标”来理解。到了链表最明显的落差是我不能再问“第几个位置在哪”而要问“从当前节点出发怎么通过 next / prev 找到下一个位置”。仅仅这一个思维转换就足以让 203 这种简单题写起来也磕磕绊绊。训练营第三天安排这三道题顺序其实是经过设计的先熟悉“删除节点怎么改指针”再强迫你实现一个完整链表类最后用反转把指针操作推向最抽象的阶段。三道题分别对应了链表操作的三个基本功删除、插入/索引、反转。说它们是入门题不如说它们是“指针操作的基本功训练场”。1.2 链表不比数组难难在“操作前先想清楚指针怎么指”数组删除一个元素后面的元素往前挪就行链表删除一个元素只需要改一次 next。听起来链表更简单但真实写代码时数组的逻辑是一眼能看穿的链表的逻辑却藏在“前一个节点的 next”里。比如删除节点 B必须拿到 B 的前驱 A然后执行A-next B-next。这句话说起来容易写的时候很多人会直接对着 B 操作结果链表断成两截。还有一个反直觉的地方链表的第 k 个节点你无法 O(1) 访问必须从头开始遍历。遍历这件事实在太基础了以至于基础到没人专门强调。可 707 设计链表里所有增删改查都建立在这个“从 head 出发移动 index 次”的过程上。如果你在遍历时拿不准“到底走几步才能到目标位置”后续所有方法都会连环出错。1.3 三道题共同的内核把三道题放在一起看它们全都在围绕两件事找前驱和改 next。203 是删除指定值的节点本质是找到“值匹配节点的前驱”707 是增删改查本质是根据索引找到前驱然后执行插入或删除206 反转链表本质是把每个节点的 next 从指向后一个改成指向前一个。一旦你从“找前驱 改 next”这个角度去理解链表很多代码就不再是死记硬背了。比如虚拟头节点为什么能简化删除逻辑因为它让“头节点也有前驱”这件事成立删除逻辑就能统一。再比如反转链表为什么双指针写法好理解因为它每一步都在做同一件小事把当前节点的 next 指向前一个节点然后整体往前挪一步。后面三个章节我会按题目逐个拆每一题都会给出完整思路、代码和避坑点。你可以按顺序读也可以直接跳到对应题目。2. 203. 移除链表元素虚拟头节点的第一次实战2.1 题目到底在问什么题目本身不长给你一个链表的头节点 head 和一个整数 val删除链表中所有满足Node.val val的节点返回新的头节点。注意“所有”这个词。也就是说不是删一个而是从头到尾把所有值等于 val 的节点都清掉。这带来一个天然麻烦如果 head 本身就要被删那么删完之后新的 head 可能是第二个节点也可能是空链表。返回值就不固定了。很多人在这个题上写出一堆 if 特判就是因为没有用虚拟头节点。我先说一个朴素思路遍历链表如果当前节点的下一个节点值等于 val就跳过它。这个思路没问题但头节点怎么处理你可以单独写一个 while 循环先把头部这些等于 val 的节点删掉再处理中间部分。这样能跑但代码分成了两段逻辑不统一。面试时一旦紧张很容易漏掉某些头部连续相同值的情况。2.2 没有虚拟头节点时删除逻辑为什么啰嗦假设链表是 1 - 2 - 3要删 1。如果我从 head 开始判断会发现 head-val 就是要删的值那 head 得变成 head-next。但删除中间节点时我不能动 head只能改前驱的 next。两种情况的动作不同必须分开写删头节点head head-next删中间节点prev-next cur-next这种“分情况讨论”本身不难问题是链表的头节点可以连续多个都等于 val。比如 1 - 1 - 1 - 2要删 1。你只把 head 往后挪一次还是会碰到 1又得再挪。于是头部需要 while 循环中间又用另一套逻辑。代码写出来又臭又长还容易在边界上出错。我训练营群里有个同学就是在这里卡了很久。他写的代码单独看每个 if 都对但连续三个相同值的头节点删到第二个时指针就乱了。原因就是删除头节点和删除中间节点用的是两套变量状态没有统一。2.3 虚拟头节点的正确姿势与代码虚拟头节点也叫 dummy head核心思想是在真正的 head 前面加一个不参与业务逻辑的节点。这样原本“没有前驱”的头节点也变成了有前驱的普通节点删除逻辑就能统一成一种如果 cur-next 的值等于 val就删除 cur-next否则 cur 向后移动。你可以把虚拟头节点理解成一个“哨兵”。它本身的值不重要重要的是它的 next 指向真正的头节点让所有节点在删除时都有一个统一的前驱。C 代码我这样写的ListNode* removeElements(ListNode* head, int val) { ListNode* dummy new ListNode(0, head); ListNode* cur dummy; while (cur-next ! nullptr) { if (cur-next-val val) { ListNode* toDelete cur-next; cur-next cur-next-next; delete toDelete; } else { cur cur-next; } } ListNode* newHead dummy-next; delete dummy; return newHead; }这里有一个细节只有匹配到 val 时才让 cur 停在原地不匹配才移动。为什么因为删掉 cur-next 之后新的 cur-next 是原来被删节点的后继它还没被检查过可能也等于 val。比如链表 1 - 1 - 2删第一个 1 后cur 还停在 dummycur-next 已经是第二个 1下一轮循环继续删。如果删完就移动 cur就会漏掉连续重复值。Python 版本更短思路一样def removeElements(self, head: ListNode, val: int) - ListNode: dummy ListNode(0, head) cur dummy while cur.next: if cur.next.val val: cur.next cur.next.next else: cur cur.next return dummy.next建议第一次接触虚拟头节点的同学把这段代码亲手画一遍。画 dummy 在最左边cur 从 dummy 出发每画一次删除就标出“谁的前驱指向谁”。画三轮之后你会彻底明白为什么这样写能统一处理头部和中间节点。2.4 我容易踩的坑头节点连续相同值这个坑我印象太深了。第一次写这个题我用的是“先处理头节点再处理中间节点”的思路。头部单独写了一个 while结果链表是 1 - 1 - 1 - 2要删 1。我的 while 条件写成了while (head ! nullptr head-val val) { head head-next; }这个写法本身没错但我在删除中间节点时又用了一个 cur 指针从 head 开始遍历。问题来了如果中间节点也出现连续两个要删的值比如 1 - 2 - 2 - 3删中间第一个 2 后cur 没有停住走到第二个 2 的前驱时前驱已经变了导致第二个 2 没删掉。用虚拟头节点之后这个坑自动消失。因为删除动作不再区分头部和中间cur 是否移动完全由“当前节点的下一个是否需要删除”来决定。这也解释了为什么虚拟头节点不是一种炫技写法而是真正降低心智负担的方案。做完这道题你顺手就掌握了一个可复用的套路涉及到可能删除头节点的链表操作优先加一个 dummy 节点。后面 707 设计链表里的 deleteAtIndex 也会用到同样的思想。3. 707. 设计链表边界条件才是这题的主菜3.1 为什么这题在训练营里很重要707 这道题要求你设计一个链表类支持 get、addAtHead、addAtTail、addAtIndex、deleteAtIndex。很多人觉得它不过是将链表基本操作封装成类实际上它是三道题里最能检验“你到底懂不懂索引和指针关系”的题目。因为你需要同时维护一个链表结构还要维护一个“索引”概念。数组里的索引是物理存在的链表的索引却是逻辑概念必须靠遍历次数来模拟。于是你每写一个方法都要问自己从 head 出发移动多少次才能到达目标节点的前驱这个问题的答案稍有偏差插入的位置就会错一个节点。我建议你先把链表结构定义清楚。可以选择单链表也可以选择带 prev 的双链表。单链表代码量少但删除节点时因为只能向前走需要找到前驱双链表多一个 prev 指针查找时可以从 head 和 tail 两头逼近删除也变得方便。我个人练习时用了双链表因为后续很多场景都要接触双链表不如一次把 prev 的逻辑也练透。3.2 用“头尾哨兵 真正索引”来设计我设计时不是直接持有 head 和 tail 节点而是用了两个哨兵节点head哨兵和tail哨兵。其中 head 哨兵的 next 指向真正第一个节点tail 哨兵的 prev 指向真正最后一个节点。初始状态下head 哨兵的 next 指向 tail 哨兵tail 哨兵的 prev 指向 head 哨兵链表为空。为什么这么做因为“空链表”和“只有一个节点”这两种状态在普通链表里很棘手。比如空链表要 addAtHeadhead 和 tail 都要变但有了哨兵之后插入操作变得非常统一我总能在 head 哨兵和它的后继之间插入或者在 tail 哨兵和它的前驱之间插入。你不需要为“空链表”写特殊分支。class 里需要记录一个 size表示当前真实节点数量。所有方法先更新 size再操作指针。顺序不要反过来否则容易乱。下面是我的结构设计struct Node { int val; Node* prev; Node* next; Node(int v) : val(v), prev(nullptr), next(nullptr) {} }; class MyLinkedList { private: Node* head; // 哨兵头 Node* tail; // 哨兵尾 int size; Node* getNode(int index) { // 从头部或尾部选择更近的方向遍历 if (index size / 2) { Node* cur head-next; for (int i 0; i index; i) cur cur-next; return cur; } else { Node* cur tail; for (int i size - 1; i index; i--) cur cur-prev; return cur; } } public: MyLinkedList() : size(0) { head new Node(0); tail new Node(0); head-next tail; tail-prev head; } // 其余方法... };这里的 getNode 是一个内部辅助函数专门根据 index 返回真实节点。用 size / 2 判断从哪头遍历是一个小优化。它不是必须的但能让 707 这种高频索引操作更高效也让你对双链表的“双向遍历”更熟悉。如果你用单链表就没有这个选择只能从头走 index 步。3.3 六个方法的实现顺序与关键判断我会按这个顺序实现get、addAtHead、addAtTail、addAtIndex、deleteAtIndex。关于 addAtIndex 和 deleteAtIndex 的 index 边界C 和 Python 版本可能略有差异但核心逻辑一致。先看 addAtIndex因为它最通用。题目要求如果 index 等于链表长度则新节点追加到尾部如果 index 大于链表长度则不插入如果 index 小于 0按 head 插入处理LeetCode 早期版本有负数 index现在边界处理可能更宽松但为了稳妥我一般还是兼容一下。如果我要在 index 位置插入需要先找到 index 位置的前驱节点 pred 和后继节点 succ。有了双链表后可以这样写if (index 0 || index size) return; if (index 0) { addAtHead(val); return; } if (index size) { addAtTail(val); return; } Node* succ getNode(index); Node* pred succ-prev; Node* newNode new Node(val); newNode-prev pred; newNode-next succ; pred-next newNode; succ-prev newNode; size;关键点在于插入前要同时拿到 pred 和 succ然后先把 newNode 的 prev 和 next 设好再去改 pred-next 和 succ-prev。顺序很重要如果你先改了 pred-next再用它来拿 succ可能就拿不到了。当然这里我们先 getNode(index) 拿到了 succ所以顺序并不致命但养成“先把新节点的两个指针都设置好再动周围节点”的习惯能避免很多诡异问题。addAtHead 和 addAtTail 可以直接复用 addAtIndex 的逻辑也可以各自独立实现void addAtHead(int val) { Node* succ head-next; Node* newNode new Node(val); newNode-prev head; newNode-next succ; head-next newNode; succ-prev newNode; size; } void addAtTail(int val) { Node* pred tail-prev; Node* newNode new Node(val); newNode-prev pred; newNode-next tail; pred-next newNode; tail-prev newNode; size; }deleteAtIndex 逻辑类似先判断 index 是否合法然后找到要删除的节点让它的前驱和后继直接相连void deleteAtIndex(int index) { if (index 0 || index size) return; Node* toDelete getNode(index); Node* pred toDelete-prev; Node* succ toDelete-next; pred-next succ; succ-prev pred; delete toDelete; size--; }get 方法就简单了index 合法后直接返回 getNode(index)-val。这里我再强调一次所有方法里size 的更新时机一致。insert 时先操作指针再 sizedelete 时先操作指针再 size--。不要在一个方法里用 size 作为循环条件同时又修改 size否则会让索引计算乱套。getNode 里我依赖 size 做遍历方向判断所以更要注意调用 getNode 时 size 必须已经是正确的值。3.4 我实测最容易写错的地方第一addAtIndex 的边界判断容易写错。LeetCode 语境下有效的插入范围是0 index size而有效删除和查询范围是0 index size。这个差异很容易被忽略插入允许等于 size删除不允许等于 size。我一开始把插入也写成index size就返回结果无法在尾部追加节点addAtTail 就废了。第二删除节点时容易忘记处理内存。C 里删除节点后要delete toDelete但如果你在 delete 之前没有保存前驱和后继后面就不能用了。先保存再改指针最后释放。很多人只改指针不释放短时间没事长时间跑内存泄漏。训练营题目不检测内存但企业面试时C 的内存管理本身就可能被追问。第三使用哨兵节点后getNode 的遍历边界容易差一。我举一个具体例子链表 size 为 3真实节点下标 0、1、2head 哨兵的下标相当于 -1tail 哨兵的下标相当于 3。如果你请求 getNode(2)从 head 出发需要走 3 步到达真实节点 2从 tail 出发需要走 1 步到达真实节点 2。这个“第几个”和“走几步”的区别是新手最容易混的地方。我的解决办法是不在脑子里算直接取一个 size1 的链表把 head 哨兵、tail 哨兵、真实节点的位置画在纸上然后推演 getNode(0)。写 707 这种事没有捷径就是反复画图、反复推演。它不像 203 那样一招鲜它需要你真正建立“链表结构 位置索引”的映射感。4. 206. 反转链表双指针法为什么比递归更直观4.1 反转的本质把所有 next 掉个头反转链表这个题思路一句话就能说完把每个节点的 next 指向它的前一个节点。但你别小看这句话。因为链表是单向的当我把某个节点的 next 改掉之后原来它指向的下一个节点就丢了。所以你必须在改之前先把下一个节点保存下来。这就是整个反转链表的核心循环保存后继改指向整体前移。数组反转可以两头交换链表反转不适用因为链表没有随机访问能力。但链表反转有一个数组没有的优点你不需要额外空间只需要几个指针O(1) 空间就能完成。这也是很多公司偏爱这个题的原因——它考察你能不能做 in-place 修改同时不丢失后续节点。我推荐你先用双指针迭代法打通思路再去碰递归。因为迭代法的每一步都非常机械跟着三个变量走就能看到链表被逐步反转。等你对迭代法滚瓜烂熟递归法只是一种写法上的优雅核心逻辑还是同一个。4.2 双指针迭代写法定义两个指针prev 初始为 nullptrcur 初始为 head。接下来循环每次做四件事保存cur-next到临时变量 tmp防止 cur 反转后丢失后继。让cur-next prev把当前节点指向前一个节点。将 prev 移动到 cur。将 cur 移动到 tmp。循环结束条件为 cur 为 nullptr。此时 prev 指向原链表的最后一个节点也就是新链表的头节点。ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* tmp cur-next; cur-next prev; prev cur; cur tmp; } return prev; }为什么第一步必须保存 tmp因为当cur-next prev执行完cur 和原来后继的连接就断了。如果之前没有把后继存下来下一步 cur 就不知道往哪走了。这个顺序一旦颠倒链表就会从中间断掉。我画图时习惯把每个节点画成一个小方块上面写 val下面画一个箭头代表 next。第一轮循环先把 1 的 next 改成 nullptr然后 prev 指向 1cur 指向 2。第二轮把 2 的 next 改成 1。画到一半你会发现原链表方向已经局部反过来了但还没反转的部分依然保持着原方向。这就是双指针法的直观画面一条从前往后走的线一边走一边把经过的箭头掉头。Python 版本几乎一样def reverseList(self, head: ListNode) - ListNode: prev None cur head while cur: tmp cur.next cur.next prev prev cur cur tmp return prev4.3 递归写法与终止边界递归写法初看很绕但我可以给你一个拆解角度递归函数 reverseList(head) 的返回值是“以 head 为起点的这段链表反转后的新头节点”。如果传进去的是头节点返回的就是原链表尾节点。递归版本可以这样写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; }假设链表是 1 - 2 - 3。reverseList(1) 会先调用 reverseList(2)reverseList(2) 会调用 reverseList(3)。因为 3 的 next 为空所以直接返回 3。回到 reverseList(2)此时 head 是 2head-next 是 3。执行head-next-next head等价于让 3 的 next 指向 2然后head-next nullptr让 2 的 next 指向空。于是 2 - 3 这一段变成了 3 - 2。回到 reverseList(1)head 是 1head-next 是 2。此时 2 的 next 已经指向 1不这里要小心在上一层已经让 3-next 2但 2-next 已经被改成 nullptr。所以这时head-next-next head等价于让 2 的 next 指向 1。再把 1 的 next 置空整条链就变成了 3 - 2 - 1。这个递归最反直觉的地方是它不是在“从前往后”反转而是在“从后往前”反转。每层递归返回之后才处理当前节点和它后继的关系。我第一次写时总觉得应该在递归前就把当前节点的 next 改掉结果写成了死循环。后来想明白递归的返回值代表“后面都已经反转好了”我只需要把当前节点放到新链表的末尾即可。递归写法的边界条件必须包含head nullptr这是为了处理空链表也包含head-next nullptr这是为了保证单节点链表直接返回。漏掉第二个条件递归会一直调用到空指针然后崩溃。4.4 画图验证的三个关键节点无论用迭代还是递归我都建议你用三个关键节点验证一下空链表、单节点链表、两个节点的链表。空链表head 为 nullptr迭代返回 prev也就是 nullptr。递归直接命中head nullptr返回 nullptr。结果都是空。单节点链表迭代时 prev 保持 nullptrcur 是唯一节点cur-next 改为 nullptr然后 prev 指向它返回 prev。递归直接命中head-next nullptr返回 head。结果都是这个节点本身。两个节点1 - 2。迭代第一轮把 1 的 next 改空第二轮把 2 的 next 改 1返回 2。递归先反转 2 - 空再把head-next-next head让 1 的 next 指向空。结果一致。这三个测试用例看着简单却能帮你快速排除“边界崩溃”和“返回节点错误”这两类高频 bug。我在训练营里见过不少人迭代法写对了但题目要求返回新头节点他返回了 cur也就是 null整个测试直接失败。其实结束循环时 cur 一定是空真正的新头被 prev 保存着。返回 prev 这件事值得在心里重复三遍。5. 三题串起来一份链表操作自查清单5.1 统一的心法先找 prev做完三道题我最大的收获不是会写某个具体功能而是总结出一句口诀链表操作几乎都在找前驱。203 删除指定值的节点找的是目标节点的前驱707 删除指定索引节点找的也是前驱707 插入时找的是新节点要插入位置之前的节点206 反转链表虽然每个节点的处理看起来是改变当前节点自己的 next但本质上你也一直在维护一个“后来者”的 prev 指针。整个训练营第三天的内容都可以被这句口诀串起来。为什么找前驱这么重要因为单链表的 next 指针是单向的你站在当前节点上知道下一个节点是谁但你不知道上一个节点是谁。想删除下一个节点我必须让“当前节点”扮演前驱角色想改变 next 指向也是拿“当前节点”下手。所有操作的落点都发生在“前驱节点”身上而不是目标节点身上。5.2 检查清单我给自己整理了一份清单每道链表题写完都按这个顺序过一遍能挡住绝大多数 bug空链表是否处理很多代码在空链表上会直接解引用空指针。头节点是否可能变化如果可能变化考虑加虚拟头节点或单独保存新头。是否需要找前驱删除需要插入需要反转看起来不需要但实际上每个节点都变成了前驱。遍历时走几步从 head 出发到目标节点是走 index 步还是 index-1 步要看目标是节点本身还是前驱。连续删除场景是否覆盖比如 203 删除连续相同值删除后 cur 不能乱移动。C 是否释放了被删除节点避免内存泄漏虽然刷题平台不校验但习惯要养好。返回值是否正确反转链表返回新头删除链表元素返回 dummy 的下一个707 的 getNode 返回真实节点而不是哨兵。这份清单不是万能的但对付训练营常见链表题已经足够。遇到复杂场景可以在纸上先画四个节点逐个推演指针变化。5.3 第三天的训练心得第二天的数组题第三天的链表题给我最直接的感觉是数据结构这种东西你只在脑子里面想和实际写出代码完全是两回事。数组我可以在脑子里模拟链表因为涉及大量指针指向光凭脑内推演特别容易出错。我后来改变策略每道题先画图再写代码。画图不需要工整只要能看清谁指向谁就行。203 教会我虚拟头节点的威力707 教会我边界条件的严谨206 教会我通过三指针或递归去维护链表的连续性。三题看起来各自独立实际上我写 707 的时候用到了 203 总结出的“先找 prev”思路写 206 的时候又用到了 707 里反复练习的“保存后继再改指针”的习惯。这种环环相扣的感觉让我觉得训练营把三道题安排在一起确实有它的道理。如果你现在也在刷这三道题我给你一个具体建议不要急着直接提交代码。先拿一个小链表比如1 - 2 - 3 - 4把 203、707、206 三个操作各手动模拟一遍。模拟到你觉得“我把每个节点的 next 从哪改到哪都清清楚楚”的时候再去写代码速度会快很多。最后说个小技巧链表题里大部分 bug都不是逻辑不懂而是“指针被覆盖后还想用原来的指向”。每次修改 next 之前先问自己一句我是不是把它原来的后继保存下来了如果保存了大胆改没保存先保存再改。这个习惯帮我少掉了很多头发。
