上个周末我帮一个朋友做模拟面试随手挑了LeetCode 19这道删除链表倒数第 N 个结点的题。他面过这道题上来就写了快慢指针代码格式和命名都很规范可我问了一句“为什么 fast 要先走 n1 步slow 要从 dummy 出发而不是从 head 出发”他愣了半天最后承认自己是背的模板。这道题在 LeetCode 上常见的主流思路一共有三类长度法、快慢指针、栈表面是三种写法内里全是链表题最经典的差一问题。如果你正准备面试或者刚开始刷链表题这篇内容想把三种解法的原理、代码、边界和踩坑经验一次讲清楚。我当时追问他三个问题链表长度怎么求倒数第 N 个结点的“前驱”是谁如果删的是头结点怎么办这三个问题答明白这道题才算真正会了。下面不绕弯子直接从头开始拆。1. 先看题倒数第 N 个天然就是单向链表的陷阱1.1 题面回顾与“倒数”的本质题目描述非常简单给定一个单链表 head删除倒数第 n 个结点返回头结点。n 是有效值也就是 1 ≤ n ≤ 链表长度。这个“有效”条件很重要它省去了很多边界校验的啰嗦但并没有省去我们对边界条件的思考。单链表的结构决定了它只能从 head 一路 next 往后走不能回头看。数组里你要删倒数第 n 个元素直接算下标 arr.length - n 就行链表不行因为链表的“下标”和内存位置没有随机访问能力。倒数第 n 个翻译成正数就是第 L - n 1 个L 为链表长度。要删的是这个节点本身可单链表删除的实质是修改前驱节点的 next所以你真正要找的是第 L - n 个节点也就是待删节点的前驱。这个“正数是第几个”和“要操作哪个指针”之间就是差一问题开始的地方。很多人写错不是代码能力不行而是没有意识到删除操作和查找操作的目标不一样。1.2 dummy 节点不是技巧是删除头结点时唯一体面的方式当待删节点恰好是头结点时它没有前驱。这时候常规的prev-next target-next根本写不出来因为 prev 不存在。新手最常见的处理是单独写一个 if 判断是不是头结点再分两条路走。我不是说这样不行而是这样的代码分支多边界容易漏。更干净的做法是新建一个哑节点 dummy让 dummy-next 指向 head。不管要删的是头结点还是中间节点在逻辑上 dummy 都充当 head 的前驱。最后返回 dummy-next 即可。用这个技巧三种解法都能把“删除头结点”和“删除普通节点”统一成同一段逻辑。我之前帮人 code review 时见过一个反面案例他用了 dummy 之后还在代码里单独判断if (n length) head head-next;看起来小心翼翼实际完全多余。记住这一条——只要加了 dummy就不要单独处理头结点。2. 解法一长度法——先数清楚再动手2.1 思路与代码两次遍历把倒数换算成正数长度法的思路最直白先完整遍历一次链表数出总长度 L。然后倒数第 n 个就是正数第 L - n 1 个删除它需要拿到第 L - n 个节点作前驱于是从 dummy 出发走 L - n 步就能停在待删节点的前驱上。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); int length 0; ListNode* cur head; while (cur) { length; cur cur-next; } // 从 dummy 出发走 length - n 步停在待删节点的前驱 ListNode* prev dummy; for (int i 0; i length - n; i) { prev prev-next; } ListNode* target prev-next; prev-next target-next; delete target; ListNode* newHead dummy-next; delete dummy; return newHead; }举个例子链表是 1 - 2 - 3 - 4 - 5n 2。L 5length - n 3。dummy 是第 0 个位置走 3 步到节点 3节点 3 正是倒数第 2 个节点也就是节点 4 的前驱。然后prev-next target-next就把 3 的 next 从 4 改到 5 了。这里的推导值得稍微展开一下。倒数第 n 个节点是正数第 L - n 1 个它的前驱是正数第 L - n 个。dummy 位于所有节点之前算第 0 个所以从 dummy 出发走 L - n 步恰好到达第 L - n 个节点。每一步都是朴素的 next 移动不需要再做加法减法。2.2 长度法的三个容易写错的地方第一统计长度时用while (cur)而不是while (cur-next)。前者走到 nullptr 才停length 正好是节点个数后者虽然也能数出长度但在空链表上会直接解引用空指针。LeetCode 的测试用例很少给空链表但本地测试时你一定会踩到。第二第二个循环的边界是i length - n不是i length - n。多加一个等号prev 就从“前驱”变成“待删节点”后面删除时你还得再记一个更前面的节点代码瞬间就从两行变成五行。第三最终必须返回dummy-next不能图省事返回 head。当 n 等于链表长度时head 就是被删除的那个节点代码里已经delete target了再返回 head 就是返回一个悬空指针本地跑起来程序直接崩。2.3 什么时候长度法并不差很多文章把长度法叫“笨办法”我不太同意。在 LeetCode 这种判断题里它确实多遍历了一次可实际工程里链表经常会自带长度字段比如标准库的 LinkedList 都有 size() 接口。如果链表类本身维护了 size长度法实际上就是一次遍历时间复杂度低逻辑也最好懂。即便没有 size 字段长度法在面试中也很有价值它是你能最快写出、最不容易出错的思路。面试时你可以先给长度法证明你会分析问题然后主动说“如果面试官要求一次遍历我还有优化方案”这比一上来就甩一个快慢指针模板要自然得多。3. 解法二快慢指针——一次遍历的真相与边界细节3.1 关键设计为什么 fast 要先走 n1 步快慢指针的代码识别度很高但真正理解它的人并不多。设计是这样的fast、slow 都从 dummy 出发fast 先走 n1 步然后 fast 和 slow 一起每次走一步。当 fast 到达 nullptr 时slow 停的位置恰好是待删节点的前驱。核心问题来了为什么是 n1不是 n假设 fast 只先走 n 步两指针之间拉开的距离是 n 个节点。fast 到末尾时slow 与末尾之间也隔着 n 个节点所以 slow 正好指向待删节点本身。可删除需要的是前驱你后面还得补一个变量记住 slow 前面的节点或者用ListNode* tmp slow-next; slow-next slow-next-next之类的写法虽然也能删但通用性差一些。让 fast 先走 n1 步slow 和 fast 之间保持 n1 个节点的距离。fast 到 nullptr 时slow 和末尾之间隔着 n1 个节点位置也就是说 slow 是倒数第 n1 个节点刚好是倒数第 n 个节点的前驱。之所以能从 dummy 出发是因为 dummy 在 head 前面补了一个位置让“删除头结点”也变成普通情况。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); ListNode* fast dummy; ListNode* slow dummy; // fast 先走 n1 步 for (int i 0; i n; i) { fast fast-next; } // 然后同步走 while (fast ! nullptr) { fast fast-next; slow slow-next; } ListNode* target slow-next; slow-next target-next; delete target; ListNode* newHead dummy-next; delete dummy; return newHead; }3.2 指针移动轨迹推演光讲概念不够我建议你自己在纸上走一遍。拿 1 - 2 - 3 - 4 - 5n 2 为例。fast 先走 3 步从 dummy 走到节点 3slow 还在 dummy。接下来进入 while 循环第 1 轮fast 从 3 走到 4slow 从 dummy 走到 1第 2 轮fast 从 4 走到 5slow 从 1 走到 2第 3 轮fast 从 5 走到 nullptrslow 从 2 走到 3此时 fast 是 nullptr循环结束slow 正好在节点 3slow-next就是待删的节点 4。这个走位非常规整但如果你把 fast 先走 n 步同样的链表最终 slow 会停在节点 4 本身多出来的那一步就是天壤之别。还有一种常见写法是 fast 先走 n 步然后让 slow 从 dummy 出发fast 走到最后一个节点fast-next nullptr时停止slow 恰好也是停在待删节点的前驱。这种写法也能跑通但我个人不推荐混搭因为“fast 先走 n1 步 循环条件 while(fast)”是一套自洽的组合改变任何一个位置都会偏差。3.3 面试追问“你能一次遍历吗”背后的考察点面试官让你优化成一次遍历考察的不是记忆力而是你有没有真正理解“用距离差模拟倒数”的思想。所以回答快慢指针时主动说出这几件事fast 和 slow 为什么要保持 n1 的距离、dummy 的作用是什么、循环终止条件为什么用while (fast ! nullptr)。如果面试官进一步问“链表能不能真的从后往前走”你可以顺势说单链表没有反向引用所以只能用这种“先发射一个探针再让慢指针跟随”的思路。这本质上是一种延迟执行现实里也有对应场景比如接收数据流时要等缓冲区积攒到一定长度再处理模式类似。空间上快慢指针只用了两个额外指针是 O(1)时间复杂度 O(L)每个节点最多被 fast 访问一次slow 再访问一次严格说常数是 2但大 O 就是 O(L)。4. 解法三栈——用空间换一种直白的思考方式4.1 把“倒数”翻译成“先进后出”快慢指针用物理距离模拟倒数栈则用先进后出的特性天然处理倒数。你只需要做两件事先把链表从头到尾压入栈然后从栈顶弹出 n 个节点。第 n 次弹出的节点就是待删节点弹出后新的栈顶恰好是它的前驱。这个解法我第一次见时觉得有点“绕”但后来想通了栈把“遍历方向”完全反转了链表从头到尾入栈栈顶就是链表尾。倒数第 n 个节点相当于正数第 n 次从栈顶弹出。算法题里当你要从尾到头处理数据时栈往往是最直接的数据结构。这里的 dummy 依然有必要。如果栈里没有 dummy删除头结点时弹出 n 次后栈可能已经空了取前驱就成了空栈操作。让 dummy 最先入栈垫底既保证了删除头结点时前驱存在又统一了代码逻辑。4.2 C 实现与内存语义ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); stackListNode* st; ListNode* cur dummy; while (cur) { st.push(cur); cur cur-next; } ListNode* target nullptr; for (int i 0; i n; i) { target st.top(); st.pop(); } ListNode* prev st.top(); // 栈里一定有 dummy所以不会空 prev-next target-next; delete target; ListNode* newHead dummy-next; delete dummy; return newHead; }注意栈里存的是ListNode*指针不是 int 值。如果你写成stackListNode每次 push 都会复制一整个节点浪费空间还改变了指针关系。这种对象拷贝的错误很隐蔽编译器不会报错但内存占用和逻辑都会出问题。空间复杂度是 O(L)因为在极端情况下整个链表都会进栈。在 n 很小的时候确实浪费但它的优势是语义直白、几乎不需要理解快慢指针的那种“距离差”技巧。面试场景下如果你前面已经讲了长度法和快慢指针再补一句“用栈也能做”会显得你掌握的不是一个孤立模板而是一整套解决问题的工具箱。4.3 栈解法的工程启发栈解法看起来只是“多了一种思路”但它在实际工程里的对应场景很常见。举个例子编辑器的撤销功能你要撤销最近一次操作本质就是把操作记录压栈然后从栈顶弹出回滚编译器检查括号匹配也是把左括号压栈遇到右括号弹栈。这道题用栈做确实不是最优空间解但它揭示了“数据结构的先进后出特性可以扭转遍历顺序”这一思想。当你以后遇到需要倒序处理线性数据的业务比如日志倒查、导航回退可以第一时间想到栈这就是刷这道题收获的一部分。5. 三种解法横评笔试、面试、工程怎么选5.1 复杂度对照表解法时间复杂度空间复杂度遍历次数代码量典型场景长度法O(L)O(1)2最少已知链表长度、思路快速验证快慢指针O(L)O(1)1中等面试首选、要求一次遍历栈O(L)O(L)1 弹出 n 个较少展示数据结构转化思路从复杂度看长度法和快慢指针的空间都是 O(1)区别只在是否允许遍历两次。实际工程里如果链表自带 size长度法反而最推荐如果是 LeetCode 面试题快慢指针最稳妥栈解法适合作为补充答案展示思维宽度。5.2 面试回答顺序与复盘要点我自己做面试官的时候最反感候选人一句话不说直接默写快慢指针。不是说快慢指针不对而是它太像“背题”。更好的回答节奏是先从长度法讲起讲清楚求长度、换算正数、找前驱这一整套逻辑然后主动优化“题目要求一次遍历的话可以用快慢指针让 fast 先走 n1 步……”如果面试官有兴趣再补栈解法。面试结束后的复盘重点看三件事是否理解 dummy 存在的意义是否能解释 fast 为什么走 n1 步是否能准确说出循环终止条件。这三个问题能答清楚就算代码写得慢一点面试官也会觉得你是真的会而不是背下来的。很多候选人背了模板一换数字就不会了就是栽在这上面。6. 实战排坑刷完这道题之后我总结的四个细节6.1 坑一返回旧 head 而不是 dummy-next我见过有人明明新建了 dummy最后却写return head;。这代码在大部分测试用例里都能过唯独 n 等于链表长度时会出问题head 指向的节点已经被 delete你返回的是一个悬空指针。C 里这个行为是未定义的本地可能崩也可能碰巧跑出随机值线上就更不可控。正确姿势永远是ListNode* newHead dummy-next;然后再 delete dummy。注意顺序先取 newHead再释放 dummy这两个操作互不影响因为 newHead 是 dummy 所指向的下一个节点释放 dummy 不会带走它。6.2 坑二本地构造链表时没有配套的释放逻辑LeetCode 的判题环境不检查内存泄漏但本地调试时如果不释放用 Valgrind 或 AddressSanitizer 一跑就是满屏报错。我刷链表题的习惯是写三个辅助函数createList、printList、freeList专门用来做本地验证。ListNode* createList(const vectorint nums) { ListNode* dummy new ListNode(0); ListNode* cur dummy; for (int num : nums) { cur-next new ListNode(num); cur cur-next; } return dummy-next; } void printList(ListNode* head) { while (head) { cout head-val - ; head head-next; } cout nullptr endl; } void freeList(ListNode* head) { while (head) { ListNode* next head-next; delete head; head next; } }有了这套辅助函数你可以针对 n1、nL、L1 三种边界反复测既验证算法正确性也让自己真正意识到“删除节点要释放内存”不是一个可有可无的动作。6.3 坑三长度法第二个循环的差一问题长度法最常见的问题出现在第二个循环。如果从 head 出发很多人会写for (int i 1; i length - n 1; i)这个循环结束之后cur 停在待删节点本身而不是它的前驱。于是你不得不额外加一个变量来记录上一个节点代码瞬间变得复杂。我推荐始终从 dummy 出发循环变量从 0 开始循环次数是 length - n。这背后的逻辑是dummy 占第 0 个位置走 length - n 次正好到达第 length - n 个节点也就是待删节点的前驱。每次循环只做prev prev-next不掺杂任何判断思路最干净。6.4 坑四快慢指针的循环条件想当然快慢指针的另一个高频错误是把while (fast ! nullptr)写成while (fast-next ! nullptr)。乍一看后者似乎是让 fast 停在最后一个节点不再往后多走一步但当你让 fast 先走 n1 步之后如果链表长度恰好是 nfast 已经是 nullptr再判断fast-next就会解引用空指针直接崩溃。即便链表长度大于 nwhile (fast-next)会让 fast 提前一个位置停止slow 跟着少走一步最终指向待删节点而不是前驱删除逻辑还是错的。我把结论说直白一点fast 先走 n1 步循环条件就用while (fast ! nullptr)这是一对固定搭配不要混搭。这道题我这几年陆陆续续刷过很多遍每次重新写都会发现自己的指针感又退步了一点。后来我总结出一个习惯写代码前先问自己三个问题——链表长度是多少我要删的节点的前驱是谁删的是头结点怎么办这三个问题想清楚长度法、快慢指针、栈的代码几乎都是水到渠成。希望这篇分析能帮你把这道经典题的差一逻辑真正刻进肌肉记忆下次再遇到链表删除能少踩一个是一个。