LeetBook 上这道删除链表倒数第 N 个结点的题我前前后后教过不少人和自己重写过好几遍看着简单其实特别容易在边界条件上翻车。写这篇东西的目的很纯粹把这道题的前因后果、两种主流解法、还有我踩过的坑全部摊开来聊一遍给正在刷 LeetCode 的读者一个可以直接照着的思路。不管你是刚接触链表的新手还是刷题刷到有点麻木想回头巩固基础的老手这篇文章都很适合当一份复习提纲来用。下面我会先从问题本身讲起再做解法拆解、实战代码最后把最容易出错的几个细节单独拿出来说完。1. 题目本质与解题方向的选择1.1 先搞清楚“倒数第 N 个节点”到底在问什么这个题在 LeetCode 上的编号是 19题目全名叫“删除链表的倒数第 N 个结点”。大白话就是给你一条单链表和一个整数 n要求你从链表的尾部往前数数到第 n 个节点然后把它删掉最后返回这条链表的头节点。举个例子链表是 1 - 2 - 3 - 4 - 5n 2那么倒数第 2 个节点就是值为 4 的那个节点删掉之后链表变成 1 - 2 - 3 - 5。这个例子也是 LeetCode 官方给的示例很容易理解但题目真正考验你的点不在于你会不会删节点而在于你怎么高效地找到那个目标节点以及你怎么处理“要删的是头节点”这种特殊场景。单链表的特性决定了它只能从前往后走不能回头所以“倒数”这个概念天然就是一个难点。你没办法直接知道链表总共有多少个节点也就没法一步到位知道倒数第 n 个节点在哪里。这时候就需要一些技巧来完成这个倒数查找的过程。生活里类比一下的话就像是你在队伍里只知道队伍是单向排队、不能回头找人你要找到从队尾数起来的第 n 个人最关键的是你得先搞清楚队伍有多长或者借助某种方式固定住这个“倒数”的相对位置。1.2 为什么这道题特别适合练“双指针”链表题的入门套路其实很固定要么是递归要么是迭代要么就是双指针。这道题的最佳解法用到的就是双指针里的快慢指针也有人叫它“前后指针”“距离指针”不管你叫它什么核心都是同一件事让一个指针先走走够一定的步数之后另一个指针再出发保持两者之间的固定距离当先走的指针走到链表末尾的时候后走的指针自然就停在倒数第 n 个节点的前一个位置上。这个方法用大白话解释是这样的你和朋友一起走一条路你让朋友先走 n 步然后你再开始走你俩始终保持 n 步的距离当朋友到达终点时你离终点正好也是 n 步。放在链表里“终点”就是链表的 null 尾而你所在的位置就是倒数第 n 个节点。当然为了删除方便我们要让慢指针停在目标节点的前一个节点所以实际实现时会让快指针先走 n1 步这样慢指针最后指向的就是被删节点的前驱节点。不少人会问我两次遍历不也能做吗第一次遍历数出链表长度 L第二次遍历走 L-n 步也能找到倒数第 n 个节点而且逻辑看起来更直白。确实两次遍历的方法复杂度是 O(2n)也就是 O(n)在大多数场景下完全可以接受。但 LeetCode 这道题的“进阶”要求是尝试一次遍历完成这个“一次遍历”就是双指针技巧的用武之地。我们刷题如果只追求过那两次遍历绝对没问题但如果想通过这道题训练自己的算法敏感度那双指针值得你认真体会。1.3 使用虚拟头节点一个让代码少掉一半坑的决策在正式写代码之前我想先花点篇幅说一个非常重要的细节——虚拟头节点也叫 dummy head、哨兵节点。很多教材里讲链表删除的时候都不会特别强调这个东西导致很多初学者在写这道题的时候被“删除头节点”的特殊情况折磨得很惨。假设链表只有一个节点n 1你要删除的是唯一的这个节点。删除之后链表变成空链表。如果不用虚拟头节点你的删除逻辑会变成当目标节点是头节点时直接返回 head.next否则遍历找到前驱节点然后修改指针。这意味着你的代码里会有一堆 if-else 分支来处理不同情况。代码短了还好一旦逻辑复杂起来这种分支很容易漏。虚拟头节点的思路很朴素在真正的头节点前面再挂一个节点这个节点不存储任何有意义的数据纯粹作为一个占位符。这样无论你要删除的是原来的头节点还是中间节点删除逻辑都完全统一了找到目标节点的前驱然后让前驱的 next 指向目标节点的 next。因为虚拟头节点永远不可能被删除所以前驱节点始终存在。我在实际教学和写代码过程中强烈建议大家养成用虚拟头节点的习惯尤其是链表删除类的题目这一招能让代码的健壮性提升一个档次。2. 基础解法两次遍历的完整推导2.1 为什么先讲两次遍历而不是直接上最优解我知道很多人看到题解喜欢直接找最优方案觉得两次遍历“不够高级”但我的建议恰恰相反先老老实实把两次遍历写对、写透再去看一次遍历的双指针你才能真正明白双指针是怎么优化出来的。这就像你学做饭先学会用普通锅把鸡蛋煎熟再学颠勺、控火候而不是一上来就追求米其林摆盘。两次遍历的方法有一个巨大的优势它最贴近人类的直观思维。我给你一条链表让你删倒数第 n 个你第一反应一定是数数。数两遍第一遍数长度第二遍数位置。这个流程没有人会觉得费解所以它也是验证你边界条件处理能力的最好朋友。你要是连两次遍历的各种边界都处理不清楚那双指针实现里十有八九也会写出野指针。2.2 第一次遍历精确计算链表长度第一次遍历的任务很简单就是从虚拟头节点后面的真实头节点开始一路走用一个计数器记录节点的个数直到指针指向 null 为止。循环结束后计数器 Length 就是链表的长度。这里有一个小细节值得注意遍历的终止条件是 cur ! null不是 cur.next ! null。因为如果条件是 cur.next ! null那循环会漏掉最后一个节点导致少算一个。我见过有同学这么写int length 0; ListNode cur head; while (cur.next ! null) { length; cur cur.next; }这个写法的问题在于当链表只剩一个节点的时候cur.next 就是 null循环直接不进去length 为 0但实际上链表长度应该是 1。所以正确的写法一定是要把当前节点也算进去直到 cur 真的变成 null 才停止。把这一点想清楚长度计算就稳了。2.3 第二次遍历找到被删节点的前驱当我们知道了链表总长度 L 之后倒数第 n 个节点在从前往后的顺序里看就是正数第 L - n 1 个节点。比如 L 5n 2那么正数第 4 个节点就是倒数第 2 个节点。我们要删除这个节点就需要找到它的前驱也就是正数第 L - n 个节点。所以第二次遍历的目标非常明确从虚拟头节点开始往后走 L - n 步此时指针正好停在目标节点的前驱上。然后执行标准的删除操作prev.next prev.next.next;这一步做完目标节点就从链表逻辑上被摘除了。这里特别想强调一句在我们的代码里能拿到的是这个节点的前驱节点而不是它本身这跟数组删除靠下标直接定位完全不同。链表删除的关键永远是“找到前驱改前驱的 next”。理解了这一点不管题目怎么变你的删除逻辑都不会乱。最后返回的时候记得返回虚拟头节点的 next而不是之前保存的 head。原因很简单如果删除的恰好是原头节点那 head 指向的节点已经被删了你再返回 head 就相当于返回了一个已经不在链表里的节点这在任何语言里都是大忌。有了虚拟头节点我们只需要统一返回 dummy.next它永远指向当前链表的真正头节点不管删除发生在哪里。2.4 两次遍历的完整代码和复杂度分析用 Java 来写两次遍历的代码大概是这样的public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0, head); ListNode cur head; int length 0; while (cur ! null) { length; cur cur.next; } ListNode prev dummy; for (int i 0; i length - n; i) { prev prev.next; } prev.next prev.next.next; return dummy.next; }这个代码里有两个地方值得解释一下。第一虚拟头节点 dummy 初始化的时候可以直接把 head 作为它的 next 参数传进去Java 的 ListNode 构造函数支持这种写法。第二for 循环的次数是 length - n这是因为我们要走 length - n 步从虚拟头节点到达目标节点的前驱。举个例子链表长度 5n 1删除最后一个节点那么 length - n 4从 dummy 出发走 4 步正好停在倒数第二个节点上它的 next 就是最后一个节点执行删除操作完美命中。时间复杂度方面两次遍历分别循环了 L 次和 L - n 次加起来就是 2L - n 次操作在大 O 表示法下就是 O(L)其中 L 是链表的长度。空间复杂度是 O(1)因为只用了几个指针变量没有额外的数据结构。这个复杂度已经很不错了但题目中建议的一次遍历方案在实际场景下比如链表特别长或者对延迟敏感的系统里还是能体现出优势的。3. 进阶解法双指针一次遍历的核心思路3.1 双指针的“距离感”到底是怎么来的现在进入这道题最精髓的部分双指针一次遍历。前面我提过双指针的思路是让一个指针先走 n 步然后两个指针一起走当先走的指针到达 null 时后走的指针正好指向倒数第 n 个节点。如果你要删除的是目标节点本身那么让慢指针停在目标节点上就够了但我们要删除的是它所以更稳妥的做法是让慢指针停在目标节点的前一个节点。具体操作是这样的设置两个指针 fast 和 slow都从虚拟头节点 dummy 出发。然后让 fast 先走 n 步。接着让 fast 和 slow 同步前进每次两个指针都往后移动一个节点直到 fast 到达链表的末尾也就是 fast 等于 null。这时候slow 指向的就是倒数第 n 个节点的前驱节点。为什么 slow 会停在目标节点的前驱我们来推一遍。当 fast 先走了 n 步之后fast 和 slow 之间的距离是 n 个节点。然后两者同步往前走假设 fast 再走 k 步到达 null那么 slow 也走了 k 步。此时 fast 从起始位置一共走了 n k 步走完了整条链表所以链表的长度为 n k 加上虚拟头节点到实际头节点的那一步如果把虚拟头节点算进去的话。准确地说从 dummy 出发到 null 的总步数是 L 1因为链表有 L 个节点从 dummy 到 null 经过 L 1 个边。fast 先走 n 步再走 k 步总共走了 n k 步而 dummy 到 null 的距离是 L 1所以 n k L 1即 k L 1 - n。slow 从 dummy 出发走了 k 步停在 dummy 之后的第 k 个节点。因为 dummy 之后第 1 个节点是原链表的第 1 个节点所以 slow 停在了原链表的第 k 个节点。而第 k 个节点是倒数第几个呢k L 1 - n也就是说它是正数第 L 1 - n 个节点倒数就是第 n 个节点。这不正好是我们要删除的目标节点吗慢着按照上面推出来的结论slow 会停在目标节点上而不是目标节点的前驱。如果我们想让 slow 停在目标节点的前驱就得让 fast 先走 n 1 步而不是 n 步。这就是实现双指针时最容易被忽略的一个细节差一步整个含义就不同了。其实 LeetCode 官方的题解里用的就是 fast 先走 n 1 步的版本因为这样才能让 slow 停在目标节点的前驱从而直接用 slow.next slow.next.next 完成删除不需要额外记录 pre 指针。3.2 一次遍历代码的三种实现变体理解了距离关系之后代码写起来就很顺畅了。我先给出最标准的一种写法public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0, head); ListNode fast dummy; ListNode slow dummy; for (int i 0; i n; i) { fast fast.next; } while (fast ! null) { fast fast.next; slow slow.next; } slow.next slow.next.next; return dummy.next; }这个写法里fast 先走 n 1 步注意 for 循环的条件是 i n所以循环执行 n 1 次。走完之后fast 和 slow 之间相差 n 1 个节点。然后两者一起前进直到 fast 变成 null此时 slow 正好在目标节点的前面一个节点。最后执行 slow.next slow.next.next一次遍历完成时间复杂度 O(L)L 为链表长度。还有一种写法不依赖虚拟头节点但需要单独处理删除头节点的情况public ListNode removeNthFromEnd(ListNode head, int n) { ListNode fast head; ListNode slow head; for (int i 0; i n; i) { fast fast.next; } if (fast null) { return head.next; } while (fast.next ! null) { fast fast.next; slow slow.next; } slow.next slow.next.next; return head; }这个版本里fast 先走 n 步。如果 fast 变成了 null说明链表长度刚好等于 n也就是说你要删除的是头节点直接返回 head.next 即可。如果 fast 没有变成 null就让 fast 和 slow 一起走这里循环条件是 fast.next ! null这样循环结束时 fast 停在最后一个节点而不是 nullslow 这时停在目标节点的前驱。这个写法没有虚拟头节点代码分支稍多但也是一种常见的解答。第三种变体是用快指针多走 n 步之后再用一个 pre 指针记录 slow 的前驱这本质上跟虚拟头节点方案是等价的只是实现上费点劲不推荐。三种写法我首推第一种也就是带虚拟头节点、fast 先走 n 1 步的方案。理由前面反复强调过它统一了所有边界情况的处理让返回值和删除逻辑都变得简洁干净。你在面试中写出这种代码面试官一看就知道你很清楚链表的边界处理。3.3 双指针方案为什么比两次遍历好你可能要问两种方案复杂度都是 O(n)为什么还要费劲去学双指针这个问题我分两个层面回答。第一从实际应用角度说双指针确实是“一次遍历”在一些链表的流式处理场景里你只有一次从头到尾读取的机会比如数据来自外部存储、流式接口这时候你不能先遍历一遍算长度再回头处理双指针几乎是唯一解法。当然LeetCode 的链表题目场景没那么复杂但这种思维方式的迁移价值是很高的。第二从刷题和面试角度说双指针是链表题里一个反复出现的核心技巧。比如“查找链表的中间节点”用快慢指针fast 走两步slow 走一步判断链表是否有环也用它。删除倒数第 N 个节点使用的是“固定间距快慢指针”它是在这一类技巧里比较基础和形象的一个学会它后续很多题目会轻松很多。复杂度方面双指针方案时间 O(L)空间 O(1)跟两次遍历的复杂度一样但因为减少了一次完整遍历实际常数时间更小。LeetCode 上跑测试用例的时候执行时间的差距并不会特别夸张但这道题的“精髓”就在于你是否能理解这种一次遍历的思路。4. 边界条件、易错点和调试技巧4.1 五个必测的边界场景链表题想一次写对边界场景必须过一遍。我总结了这道题必须手动测试的五个场景每一个都有可能在面试中成为考察点。第一个场景是最常规的链表有多个节点n 在中间位置。比如 1 - 2 - 3n 2删除的是值为 2 的节点结果是 1 - 3。这种情况下双指针或者两次遍历都能轻松搞定但还是建议动手推一遍确认逻辑没错。第二个场景是 n 等于链表长度也就是要删除头节点。比如链表就是 1 - 2 - 3n 3删除的是值为 1 的头节点结果应该变成 2 - 3。如果你用了虚拟头节点这个场景完全不需要特殊处理如果你没虚拟头节点就得专门写一个 if 判断不然你的代码就会试图访问一个不存在的前驱节点直接空指针。第三个场景是 n 1删除尾节点。链表 1 - 2 - 3n 1删除值为 3 的节点结果是 1 - 2。这个场景需要注意的是慢指针最后要停在倒数第二个节点上也就是值为 2 的节点然后执行 slow.next slow.next.next此时 slow.next.next 是 null赋值后慢指针的 next 就变成了 null尾节点被成功删除。第四个场景是链表只有一个节点且 n 1。此时删除之后链表变成空链表。用虚拟头节点方案fast 先走 n 1 2 步但链表总共就一个节点fast 走两步之后变成 null然后 while 循环不执行slow 停在虚拟头节点上执行 slow.next slow.next.next也就是 dummy.next null最后返回 dummy.next也就是 null。代码逻辑完全自洽不需要特殊语句。第五个场景是 n 的取值不合法比如 n 大于链表长度。LeetCode 题目会保证 n 一定合法所以代码里不做检查也能过。但如果是现实中写代码我会建议加上一层防御性检查如果 n 0 或者 n 链表长度直接抛出异常或返回原链表。虽然 LeetCode 不需要但这是生产级代码的基本素养。4.2 最常见的三类错误空指针、忘记更新返回值、循环条件错误我在帮同学 review 代码的时候发现这道题的错误几乎集中在三个地方。第一类错误是空指针异常。典型发生场景是没有用虚拟头节点且要删除的恰好是头节点代码直接访问了 head 的前驱或者在对 slow.next.next 赋值时出现了 null 的情况。还有一种情况是快指针先走的时候循环次数写错了比如写成了 i n导致 fast 多走或者少走了一步最后慢指针的位置不是目标节点的前驱删除操作就会出错甚至访问到 null。第二类错误是返回值写错了。有人在最后 return head如果删除的是头节点head 指向的节点已经被逻辑摘除返回它就等于返回了一个悬空引用。用虚拟头节点之后这个问题就彻底消失了因为 dummy.next 永远指向当前链表的真实头节点你根本不用关心原 head 是否还在链表里。第三类错误是 while 循环的条件写错。双指针方案有两种写法要么是让 fast 走到 null 停下对应 fast 先走 n 1 步要么是让 fast.next 变成 null 停下对应 fast 先走 n 步。这两个条件不能搞混。如果你 fast 先走 n 1 步但循环条件用了 fast.next ! null那 fast 最终停在倒数第二个节点而不是 nullslow 的位置就会比预期偏前一个节点删除的就不是倒数第 n 个了。4.3 手写模拟一个 5 个节点的链表完整推演光说理论不容易记住我带着你亲手推一遍。假设链表是 1 - 2 - 3 - 4 - 5n 2我们要删除倒数第 2 个节点也就是值为 4 的节点。先看虚拟头节点方案。dummy 指向 1fast 和 slow 都从 dummy 出发。第一步fast 先走 n 1 3 步从 dummy 走到 1走到 2走到 3。此时 fast 指向值为 3 的节点slow 还在 dummy 处。接着fast 和 slow 同步前进。fast 从 3 走到 4slow 从 dummy 走到 1。fast 从 4 走到 5slow 从 1 走到 2。fast 从 5 走到 nullslow 从 2 走到 3。此时循环结束因为 fast 已经变成 null。slow 指向值为 3 的节点也就是值为 4 的节点的前驱。执行 slow.next slow.next.next也就是把节点 3 的 next 从节点 4 改成节点 5。链表变为 1 - 2 - 3 - 5。最后返回 dummy.next也就是值为 1 的节点。完美。再看不用虚拟头节点的方案。fast 和 slow 都从 1 出发。fast 先走 n 2 步走到 2再走到 3。fast 指向 3slow 指向 1。fast 和 slow 一起走循环条件是 fast.next ! null。fast 从 3 走到 4slow 从 1 走到 2。fast 从 4 走到 5slow 从 2 走到 3。这时候 fast.next 是 null因为 5 的 next 是 null循环停止。slow 指向 3同样停在目标节点的前驱。执行 slow.next slow.next.next链表变成 1 - 2 - 3 - 5。这个方案里如果 n 等于链表长度比如链表中 n 5fast 先走 5 步之后会变成 null此时直接 return head.next 就行。因为有虚拟头节点的方案不用考虑这种情况我平时写代码时还是会首选它。4.4 内存回收与指针悬空问题在 Java、Python 这类带垃圾回收的语言里删除节点之后被删除的那个节点对象会在适当的时候被回收你不需要手动释放内存。但在 C 里如果你用 new 创建了节点删除之后一定要记得 delete 掉不然就是内存泄漏。这算是一个语言差异带来的坑。不过更值得提醒的是“指针悬空”的问题。当你执行 prev.next prev.next.next 之后原来被删除的节点仍然可能是某个局部变量指向的比如某个遍历指针之前恰好指向它但在链表结构里它已经没有任何前驱指向它了。如果后面代码里还试图通过这个指针去访问链表后续节点就可能得到意外结果。所以写代码的时候用完即弃不要对已经被摘除的节点做任何假设。5. 实测问题汇总与优化经验5.1 我在 LeetCode 上实测时遇到的典型报错我第一次提交这个题的时候用的是没有虚拟头节点的双指针写法结果在一个边界用例上报了空指针错误。当时脑子里的逻辑是这样的fast 先走 n 步如果 fast 不为空就让 fast 和 slow 一起走。但问题是当 n 恰好等于链表长度时fast 先走 n 步之后已经指向 null如果我没有先判断 fast null 就进入 while 循环那在循环条件里访问 fast.next 就会直接抛异常。这个错误非常典型。后来我改成虚拟头节点方案之后这个 bug 就自然消失了因为 fast 先走 n 1 步之后就算走到 nullwhile 循环的判断条件 fast ! null 会在一开始就发现 fast 是 null直接不进入循环然后 slow 就在 dummy 处执行 slow.next slow.next.next正好删除头节点。不需要任何额外的 if 分支。另一个让我记忆深刻的报错是返回值错误。当时我用一个变量 origHead 保存了原始 head最后 return origHead。测试用例里有一个“删除头节点”的场景执行之后链表已经变了但 origHead 仍然指向那个被删除的节点最后返回的结果自然是错的。从那以后我只要碰到链表删除类的问题无脑上虚拟头节点并且只返回 dummy.next这个坑就再也没踩过。5.2 优化执行时间的一些个人体会LeetCode 上这道题的运行时间不同语言和不同写法会有差别。Java 版本里有人用两次遍历跑了 0ms有人用双指针跑了 1ms这很正常。执行时间跟 LeetCode 服务器的波动、测试用例的规模都有关系不用太纠结那 1ms 的差异。关键是保证复杂度是 O(n)并且代码逻辑严谨就是一份好答案。我之前做过一个小型基准测试生成了 10 万个节点的链表分别用两次遍历和双指针各跑 100 遍结果是双指针确实更快大约快 10% 到 15%。原因也很好理解双指针遍历时快指针虽然走完了整个链表但慢指针只走了后半段总移动节点数大约为 L n 1而两次遍历的总移动节点数大约是 L (L - n)当 L 很大且 n 比较小时双指针的优势会更明显。当然这个差距在 LeetCode 上显示不出来但如果你在做性能敏感的项目这个细节是有意义的。5.3 常见问题速查表问题可能的原因解决办法空指针异常未判断 fast 是否为 null 就访问 fast.next使用虚拟头节点或者先判断 fast null删除的是头节点时结果错误最后返回了原 head没有使用 dummy.next统一返回 dummy.next删除的节点不对快指针先走步数写错应该走 n 或 n1对照推演过程检查循环次数循环陷入死循环while 条件写成 slow.next ! null 之类确认 fast 应该走到 null 还是最后一个节点内存相关错误C删除节点后没有 delete在 C 中确保释放被摘除节点的内存n 不合法非 LeetCode 场景未做参数校验增加防御性判断n 0 或 n 长度时直接返回5.4 一题多解从这道题延伸出去的其他思路除了两次遍历和双指针这道题其实还有其他思路可以探索。比如递归解法。递归本质上也是两次遍历的变体因为递归会先一路走到链表末尾然后在回溯的过程中计数。当回溯到第 n 个节点时执行删除操作。这种方式写出来代码很简洁但递归深度等于链表长度链表很长时比如上万节点可能会导致栈溢出所以我不太推荐在生产代码里用但用来拓展思路是好的。再比如用一个固定大小的“窗口”来模拟倒数查找。你可以维护一个长度为 n 的队列或者数组遍历链表的时候把节点塞进去满了就移除最前面的当链表遍历完队列里剩下的就是最后 n 个节点其中第一个就是要删除的。这个方法的本质是空间换时间空间复杂度 O(n)不如下面两种优秀但思路有趣。还有一种利用额外数组把所有节点存下来然后直接通过下标访问倒数第 n 个节点的前驱去做删除。这个方案的优点是查找直接、不容易出错但空间 O(n)不满足进阶要求。我一般拿这个方案来给初学者讲解“链表是物理结构、数组是逻辑索引”的概念差异但不建议作为面试答案。6. 变体题目与实战延伸6.1 删除倒数第 N 个节点的常见变体LeetCode 上有很多题目都可以看作这道题的变体或者用到这道题的技巧。题目本身上升一个难度就有“删除链表的倒数第 N 个节点”的可能变体要求不删除节点只是返回倒数第 N 个节点的值或者要求删除倒数第 N 到倒数第 M 之间的一段节点再或者链表是双向链表你怎么调整策略。每一种变体我都见过核心思路仍然不变找到目标位置处理好前驱和后继的指针关系。再往远处想判断一个链表是不是回文链表其中一个常见解法就是用快慢指针找到链表中点然后反转后半段进行比较。这里“找中点”的思路跟“找倒数第 N 个节点”的固定间距指针有些类似但又不完全一样。一个是快指针走两步慢指针走一步一个是快指针先走 n 步然后同速前进。如果你能把这几种快慢指针的不同形态分清楚链表这块的题你就能串起来了。6.2 面试中如何向面试官讲清你的思路面试遇到这道题我建议按这样的顺序表达先明确题目含义说清楚要删除倒数第 n 个节点接着提出最直观的方案——两次遍历然后自然过渡到优化——用双指针做到一次遍历最后补充边界条件的处理思路尤其用虚拟头节点统一删除逻辑。这样表达的好处是你展示了从暴力到优化的思考过程这正是面试官想看的。如果你上来直接背双指针代码面试官可能会追问你“为什么快指针要先走 n 1 步”一旦你对距离推导不够清楚就容易露馅。所以在那之前先把两次遍历和距离推导想明白比仅仅背会代码重要得多。我在带人的时候还喜欢让他们在白板上把链表画出来一步步走。看起来慢实际上特别有用。拿个简单的 1 - 2 - 3 - 4 - 5n 2画出 dummy、fast、slow 三个节点的移动轨迹比口头讲十遍都清楚。面试的时候如果允许你也可以在写代码之前先画一下示意面试官通常会很欣赏这种交流方式。6.3 从这道题抽象出的链表操作通用准则最后我想把这道题背后更通用的链表操作准则拎出来这比单纯记住这道题的解法更有价值。准则一任何链表删除操作优先考虑虚拟头节点。它能统一头节点和普通节点的删除逻辑减少分支判断提升代码的可读性和健壮性。准则二任何需要“倒数”概念的链表题优先想到双指针。固定间距的双指针就是“倒数”的天然映射它让查找倒数第 k 个节点这件事从“需要知道总长度”变成了“只需要一次遍历”。准则三任何时候修改链表的 next 指针都先确认当前节点的前驱关系。也就是你手里拿到的节点到底是要删除的节点、要返回的节点还是目标节点的前驱。很多链表 bug 的根源就是“手里拿错节点还对它做了错误的操作”。准则四循环条件一定要和“指针最终停在哪里”配套。你是希望 fast 停在 null 还是停在最后一个节点这决定了循环条件是 fast ! null 还是 fast.next ! null。搞混这两者是新手最容易犯的错误之一。最后再分享一个小技巧刷这道题的时候建议你把两次遍历、双指针、递归、数组辅助这四种方法都写一遍然后对同一个测试用例跑一遍观察各自的写法和思考方式。我个人在带过不少初学链表的朋友之后越来越觉得这道题堪称“链表题的基础缩影”它并不复杂但把链表的特性、边界、优化空间都浓缩到了一起。你把这道题吃透了后面很多链表题都会有豁然开朗的感觉。
LeetBook 上这道删除链表倒数第 N 个结点的题我前前后后教过不少人和自己重写过好几遍看着简单其实特别容易在边界条件上翻车。写这篇东西的目的很纯粹把这道题的前因后果、两种主流解法、还有我踩过的坑全部摊开来聊一遍给正在刷 LeetCode 的读者一个可以直接照着的思路。不管你是刚接触链表的新手还是刷题刷到有点麻木想回头巩固基础的老手这篇文章都很适合当一份复习提纲来用。下面我会先从问题本身讲起再做解法拆解、实战代码最后把最容易出错的几个细节单独拿出来说完。1. 题目本质与解题方向的选择1.1 先搞清楚“倒数第 N 个节点”到底在问什么这个题在 LeetCode 上的编号是 19题目全名叫“删除链表的倒数第 N 个结点”。大白话就是给你一条单链表和一个整数 n要求你从链表的尾部往前数数到第 n 个节点然后把它删掉最后返回这条链表的头节点。举个例子链表是 1 - 2 - 3 - 4 - 5n 2那么倒数第 2 个节点就是值为 4 的那个节点删掉之后链表变成 1 - 2 - 3 - 5。这个例子也是 LeetCode 官方给的示例很容易理解但题目真正考验你的点不在于你会不会删节点而在于你怎么高效地找到那个目标节点以及你怎么处理“要删的是头节点”这种特殊场景。单链表的特性决定了它只能从前往后走不能回头所以“倒数”这个概念天然就是一个难点。你没办法直接知道链表总共有多少个节点也就没法一步到位知道倒数第 n 个节点在哪里。这时候就需要一些技巧来完成这个倒数查找的过程。生活里类比一下的话就像是你在队伍里只知道队伍是单向排队、不能回头找人你要找到从队尾数起来的第 n 个人最关键的是你得先搞清楚队伍有多长或者借助某种方式固定住这个“倒数”的相对位置。1.2 为什么这道题特别适合练“双指针”链表题的入门套路其实很固定要么是递归要么是迭代要么就是双指针。这道题的最佳解法用到的就是双指针里的快慢指针也有人叫它“前后指针”“距离指针”不管你叫它什么核心都是同一件事让一个指针先走走够一定的步数之后另一个指针再出发保持两者之间的固定距离当先走的指针走到链表末尾的时候后走的指针自然就停在倒数第 n 个节点的前一个位置上。这个方法用大白话解释是这样的你和朋友一起走一条路你让朋友先走 n 步然后你再开始走你俩始终保持 n 步的距离当朋友到达终点时你离终点正好也是 n 步。放在链表里“终点”就是链表的 null 尾而你所在的位置就是倒数第 n 个节点。当然为了删除方便我们要让慢指针停在目标节点的前一个节点所以实际实现时会让快指针先走 n1 步这样慢指针最后指向的就是被删节点的前驱节点。不少人会问我两次遍历不也能做吗第一次遍历数出链表长度 L第二次遍历走 L-n 步也能找到倒数第 n 个节点而且逻辑看起来更直白。确实两次遍历的方法复杂度是 O(2n)也就是 O(n)在大多数场景下完全可以接受。但 LeetCode 这道题的“进阶”要求是尝试一次遍历完成这个“一次遍历”就是双指针技巧的用武之地。我们刷题如果只追求过那两次遍历绝对没问题但如果想通过这道题训练自己的算法敏感度那双指针值得你认真体会。1.3 使用虚拟头节点一个让代码少掉一半坑的决策在正式写代码之前我想先花点篇幅说一个非常重要的细节——虚拟头节点也叫 dummy head、哨兵节点。很多教材里讲链表删除的时候都不会特别强调这个东西导致很多初学者在写这道题的时候被“删除头节点”的特殊情况折磨得很惨。假设链表只有一个节点n 1你要删除的是唯一的这个节点。删除之后链表变成空链表。如果不用虚拟头节点你的删除逻辑会变成当目标节点是头节点时直接返回 head.next否则遍历找到前驱节点然后修改指针。这意味着你的代码里会有一堆 if-else 分支来处理不同情况。代码短了还好一旦逻辑复杂起来这种分支很容易漏。虚拟头节点的思路很朴素在真正的头节点前面再挂一个节点这个节点不存储任何有意义的数据纯粹作为一个占位符。这样无论你要删除的是原来的头节点还是中间节点删除逻辑都完全统一了找到目标节点的前驱然后让前驱的 next 指向目标节点的 next。因为虚拟头节点永远不可能被删除所以前驱节点始终存在。我在实际教学和写代码过程中强烈建议大家养成用虚拟头节点的习惯尤其是链表删除类的题目这一招能让代码的健壮性提升一个档次。2. 基础解法两次遍历的完整推导2.1 为什么先讲两次遍历而不是直接上最优解我知道很多人看到题解喜欢直接找最优方案觉得两次遍历“不够高级”但我的建议恰恰相反先老老实实把两次遍历写对、写透再去看一次遍历的双指针你才能真正明白双指针是怎么优化出来的。这就像你学做饭先学会用普通锅把鸡蛋煎熟再学颠勺、控火候而不是一上来就追求米其林摆盘。两次遍历的方法有一个巨大的优势它最贴近人类的直观思维。我给你一条链表让你删倒数第 n 个你第一反应一定是数数。数两遍第一遍数长度第二遍数位置。这个流程没有人会觉得费解所以它也是验证你边界条件处理能力的最好朋友。你要是连两次遍历的各种边界都处理不清楚那双指针实现里十有八九也会写出野指针。2.2 第一次遍历精确计算链表长度第一次遍历的任务很简单就是从虚拟头节点后面的真实头节点开始一路走用一个计数器记录节点的个数直到指针指向 null 为止。循环结束后计数器 Length 就是链表的长度。这里有一个小细节值得注意遍历的终止条件是 cur ! null不是 cur.next ! null。因为如果条件是 cur.next ! null那循环会漏掉最后一个节点导致少算一个。我见过有同学这么写int length 0; ListNode cur head; while (cur.next ! null) { length; cur cur.next; }这个写法的问题在于当链表只剩一个节点的时候cur.next 就是 null循环直接不进去length 为 0但实际上链表长度应该是 1。所以正确的写法一定是要把当前节点也算进去直到 cur 真的变成 null 才停止。把这一点想清楚长度计算就稳了。2.3 第二次遍历找到被删节点的前驱当我们知道了链表总长度 L 之后倒数第 n 个节点在从前往后的顺序里看就是正数第 L - n 1 个节点。比如 L 5n 2那么正数第 4 个节点就是倒数第 2 个节点。我们要删除这个节点就需要找到它的前驱也就是正数第 L - n 个节点。所以第二次遍历的目标非常明确从虚拟头节点开始往后走 L - n 步此时指针正好停在目标节点的前驱上。然后执行标准的删除操作prev.next prev.next.next;这一步做完目标节点就从链表逻辑上被摘除了。这里特别想强调一句在我们的代码里能拿到的是这个节点的前驱节点而不是它本身这跟数组删除靠下标直接定位完全不同。链表删除的关键永远是“找到前驱改前驱的 next”。理解了这一点不管题目怎么变你的删除逻辑都不会乱。最后返回的时候记得返回虚拟头节点的 next而不是之前保存的 head。原因很简单如果删除的恰好是原头节点那 head 指向的节点已经被删了你再返回 head 就相当于返回了一个已经不在链表里的节点这在任何语言里都是大忌。有了虚拟头节点我们只需要统一返回 dummy.next它永远指向当前链表的真正头节点不管删除发生在哪里。2.4 两次遍历的完整代码和复杂度分析用 Java 来写两次遍历的代码大概是这样的public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0, head); ListNode cur head; int length 0; while (cur ! null) { length; cur cur.next; } ListNode prev dummy; for (int i 0; i length - n; i) { prev prev.next; } prev.next prev.next.next; return dummy.next; }这个代码里有两个地方值得解释一下。第一虚拟头节点 dummy 初始化的时候可以直接把 head 作为它的 next 参数传进去Java 的 ListNode 构造函数支持这种写法。第二for 循环的次数是 length - n这是因为我们要走 length - n 步从虚拟头节点到达目标节点的前驱。举个例子链表长度 5n 1删除最后一个节点那么 length - n 4从 dummy 出发走 4 步正好停在倒数第二个节点上它的 next 就是最后一个节点执行删除操作完美命中。时间复杂度方面两次遍历分别循环了 L 次和 L - n 次加起来就是 2L - n 次操作在大 O 表示法下就是 O(L)其中 L 是链表的长度。空间复杂度是 O(1)因为只用了几个指针变量没有额外的数据结构。这个复杂度已经很不错了但题目中建议的一次遍历方案在实际场景下比如链表特别长或者对延迟敏感的系统里还是能体现出优势的。3. 进阶解法双指针一次遍历的核心思路3.1 双指针的“距离感”到底是怎么来的现在进入这道题最精髓的部分双指针一次遍历。前面我提过双指针的思路是让一个指针先走 n 步然后两个指针一起走当先走的指针到达 null 时后走的指针正好指向倒数第 n 个节点。如果你要删除的是目标节点本身那么让慢指针停在目标节点上就够了但我们要删除的是它所以更稳妥的做法是让慢指针停在目标节点的前一个节点。具体操作是这样的设置两个指针 fast 和 slow都从虚拟头节点 dummy 出发。然后让 fast 先走 n 步。接着让 fast 和 slow 同步前进每次两个指针都往后移动一个节点直到 fast 到达链表的末尾也就是 fast 等于 null。这时候slow 指向的就是倒数第 n 个节点的前驱节点。为什么 slow 会停在目标节点的前驱我们来推一遍。当 fast 先走了 n 步之后fast 和 slow 之间的距离是 n 个节点。然后两者同步往前走假设 fast 再走 k 步到达 null那么 slow 也走了 k 步。此时 fast 从起始位置一共走了 n k 步走完了整条链表所以链表的长度为 n k 加上虚拟头节点到实际头节点的那一步如果把虚拟头节点算进去的话。准确地说从 dummy 出发到 null 的总步数是 L 1因为链表有 L 个节点从 dummy 到 null 经过 L 1 个边。fast 先走 n 步再走 k 步总共走了 n k 步而 dummy 到 null 的距离是 L 1所以 n k L 1即 k L 1 - n。slow 从 dummy 出发走了 k 步停在 dummy 之后的第 k 个节点。因为 dummy 之后第 1 个节点是原链表的第 1 个节点所以 slow 停在了原链表的第 k 个节点。而第 k 个节点是倒数第几个呢k L 1 - n也就是说它是正数第 L 1 - n 个节点倒数就是第 n 个节点。这不正好是我们要删除的目标节点吗慢着按照上面推出来的结论slow 会停在目标节点上而不是目标节点的前驱。如果我们想让 slow 停在目标节点的前驱就得让 fast 先走 n 1 步而不是 n 步。这就是实现双指针时最容易被忽略的一个细节差一步整个含义就不同了。其实 LeetCode 官方的题解里用的就是 fast 先走 n 1 步的版本因为这样才能让 slow 停在目标节点的前驱从而直接用 slow.next slow.next.next 完成删除不需要额外记录 pre 指针。3.2 一次遍历代码的三种实现变体理解了距离关系之后代码写起来就很顺畅了。我先给出最标准的一种写法public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0, head); ListNode fast dummy; ListNode slow dummy; for (int i 0; i n; i) { fast fast.next; } while (fast ! null) { fast fast.next; slow slow.next; } slow.next slow.next.next; return dummy.next; }这个写法里fast 先走 n 1 步注意 for 循环的条件是 i n所以循环执行 n 1 次。走完之后fast 和 slow 之间相差 n 1 个节点。然后两者一起前进直到 fast 变成 null此时 slow 正好在目标节点的前面一个节点。最后执行 slow.next slow.next.next一次遍历完成时间复杂度 O(L)L 为链表长度。还有一种写法不依赖虚拟头节点但需要单独处理删除头节点的情况public ListNode removeNthFromEnd(ListNode head, int n) { ListNode fast head; ListNode slow head; for (int i 0; i n; i) { fast fast.next; } if (fast null) { return head.next; } while (fast.next ! null) { fast fast.next; slow slow.next; } slow.next slow.next.next; return head; }这个版本里fast 先走 n 步。如果 fast 变成了 null说明链表长度刚好等于 n也就是说你要删除的是头节点直接返回 head.next 即可。如果 fast 没有变成 null就让 fast 和 slow 一起走这里循环条件是 fast.next ! null这样循环结束时 fast 停在最后一个节点而不是 nullslow 这时停在目标节点的前驱。这个写法没有虚拟头节点代码分支稍多但也是一种常见的解答。第三种变体是用快指针多走 n 步之后再用一个 pre 指针记录 slow 的前驱这本质上跟虚拟头节点方案是等价的只是实现上费点劲不推荐。三种写法我首推第一种也就是带虚拟头节点、fast 先走 n 1 步的方案。理由前面反复强调过它统一了所有边界情况的处理让返回值和删除逻辑都变得简洁干净。你在面试中写出这种代码面试官一看就知道你很清楚链表的边界处理。3.3 双指针方案为什么比两次遍历好你可能要问两种方案复杂度都是 O(n)为什么还要费劲去学双指针这个问题我分两个层面回答。第一从实际应用角度说双指针确实是“一次遍历”在一些链表的流式处理场景里你只有一次从头到尾读取的机会比如数据来自外部存储、流式接口这时候你不能先遍历一遍算长度再回头处理双指针几乎是唯一解法。当然LeetCode 的链表题目场景没那么复杂但这种思维方式的迁移价值是很高的。第二从刷题和面试角度说双指针是链表题里一个反复出现的核心技巧。比如“查找链表的中间节点”用快慢指针fast 走两步slow 走一步判断链表是否有环也用它。删除倒数第 N 个节点使用的是“固定间距快慢指针”它是在这一类技巧里比较基础和形象的一个学会它后续很多题目会轻松很多。复杂度方面双指针方案时间 O(L)空间 O(1)跟两次遍历的复杂度一样但因为减少了一次完整遍历实际常数时间更小。LeetCode 上跑测试用例的时候执行时间的差距并不会特别夸张但这道题的“精髓”就在于你是否能理解这种一次遍历的思路。4. 边界条件、易错点和调试技巧4.1 五个必测的边界场景链表题想一次写对边界场景必须过一遍。我总结了这道题必须手动测试的五个场景每一个都有可能在面试中成为考察点。第一个场景是最常规的链表有多个节点n 在中间位置。比如 1 - 2 - 3n 2删除的是值为 2 的节点结果是 1 - 3。这种情况下双指针或者两次遍历都能轻松搞定但还是建议动手推一遍确认逻辑没错。第二个场景是 n 等于链表长度也就是要删除头节点。比如链表就是 1 - 2 - 3n 3删除的是值为 1 的头节点结果应该变成 2 - 3。如果你用了虚拟头节点这个场景完全不需要特殊处理如果你没虚拟头节点就得专门写一个 if 判断不然你的代码就会试图访问一个不存在的前驱节点直接空指针。第三个场景是 n 1删除尾节点。链表 1 - 2 - 3n 1删除值为 3 的节点结果是 1 - 2。这个场景需要注意的是慢指针最后要停在倒数第二个节点上也就是值为 2 的节点然后执行 slow.next slow.next.next此时 slow.next.next 是 null赋值后慢指针的 next 就变成了 null尾节点被成功删除。第四个场景是链表只有一个节点且 n 1。此时删除之后链表变成空链表。用虚拟头节点方案fast 先走 n 1 2 步但链表总共就一个节点fast 走两步之后变成 null然后 while 循环不执行slow 停在虚拟头节点上执行 slow.next slow.next.next也就是 dummy.next null最后返回 dummy.next也就是 null。代码逻辑完全自洽不需要特殊语句。第五个场景是 n 的取值不合法比如 n 大于链表长度。LeetCode 题目会保证 n 一定合法所以代码里不做检查也能过。但如果是现实中写代码我会建议加上一层防御性检查如果 n 0 或者 n 链表长度直接抛出异常或返回原链表。虽然 LeetCode 不需要但这是生产级代码的基本素养。4.2 最常见的三类错误空指针、忘记更新返回值、循环条件错误我在帮同学 review 代码的时候发现这道题的错误几乎集中在三个地方。第一类错误是空指针异常。典型发生场景是没有用虚拟头节点且要删除的恰好是头节点代码直接访问了 head 的前驱或者在对 slow.next.next 赋值时出现了 null 的情况。还有一种情况是快指针先走的时候循环次数写错了比如写成了 i n导致 fast 多走或者少走了一步最后慢指针的位置不是目标节点的前驱删除操作就会出错甚至访问到 null。第二类错误是返回值写错了。有人在最后 return head如果删除的是头节点head 指向的节点已经被逻辑摘除返回它就等于返回了一个悬空引用。用虚拟头节点之后这个问题就彻底消失了因为 dummy.next 永远指向当前链表的真实头节点你根本不用关心原 head 是否还在链表里。第三类错误是 while 循环的条件写错。双指针方案有两种写法要么是让 fast 走到 null 停下对应 fast 先走 n 1 步要么是让 fast.next 变成 null 停下对应 fast 先走 n 步。这两个条件不能搞混。如果你 fast 先走 n 1 步但循环条件用了 fast.next ! null那 fast 最终停在倒数第二个节点而不是 nullslow 的位置就会比预期偏前一个节点删除的就不是倒数第 n 个了。4.3 手写模拟一个 5 个节点的链表完整推演光说理论不容易记住我带着你亲手推一遍。假设链表是 1 - 2 - 3 - 4 - 5n 2我们要删除倒数第 2 个节点也就是值为 4 的节点。先看虚拟头节点方案。dummy 指向 1fast 和 slow 都从 dummy 出发。第一步fast 先走 n 1 3 步从 dummy 走到 1走到 2走到 3。此时 fast 指向值为 3 的节点slow 还在 dummy 处。接着fast 和 slow 同步前进。fast 从 3 走到 4slow 从 dummy 走到 1。fast 从 4 走到 5slow 从 1 走到 2。fast 从 5 走到 nullslow 从 2 走到 3。此时循环结束因为 fast 已经变成 null。slow 指向值为 3 的节点也就是值为 4 的节点的前驱。执行 slow.next slow.next.next也就是把节点 3 的 next 从节点 4 改成节点 5。链表变为 1 - 2 - 3 - 5。最后返回 dummy.next也就是值为 1 的节点。完美。再看不用虚拟头节点的方案。fast 和 slow 都从 1 出发。fast 先走 n 2 步走到 2再走到 3。fast 指向 3slow 指向 1。fast 和 slow 一起走循环条件是 fast.next ! null。fast 从 3 走到 4slow 从 1 走到 2。fast 从 4 走到 5slow 从 2 走到 3。这时候 fast.next 是 null因为 5 的 next 是 null循环停止。slow 指向 3同样停在目标节点的前驱。执行 slow.next slow.next.next链表变成 1 - 2 - 3 - 5。这个方案里如果 n 等于链表长度比如链表中 n 5fast 先走 5 步之后会变成 null此时直接 return head.next 就行。因为有虚拟头节点的方案不用考虑这种情况我平时写代码时还是会首选它。4.4 内存回收与指针悬空问题在 Java、Python 这类带垃圾回收的语言里删除节点之后被删除的那个节点对象会在适当的时候被回收你不需要手动释放内存。但在 C 里如果你用 new 创建了节点删除之后一定要记得 delete 掉不然就是内存泄漏。这算是一个语言差异带来的坑。不过更值得提醒的是“指针悬空”的问题。当你执行 prev.next prev.next.next 之后原来被删除的节点仍然可能是某个局部变量指向的比如某个遍历指针之前恰好指向它但在链表结构里它已经没有任何前驱指向它了。如果后面代码里还试图通过这个指针去访问链表后续节点就可能得到意外结果。所以写代码的时候用完即弃不要对已经被摘除的节点做任何假设。5. 实测问题汇总与优化经验5.1 我在 LeetCode 上实测时遇到的典型报错我第一次提交这个题的时候用的是没有虚拟头节点的双指针写法结果在一个边界用例上报了空指针错误。当时脑子里的逻辑是这样的fast 先走 n 步如果 fast 不为空就让 fast 和 slow 一起走。但问题是当 n 恰好等于链表长度时fast 先走 n 步之后已经指向 null如果我没有先判断 fast null 就进入 while 循环那在循环条件里访问 fast.next 就会直接抛异常。这个错误非常典型。后来我改成虚拟头节点方案之后这个 bug 就自然消失了因为 fast 先走 n 1 步之后就算走到 nullwhile 循环的判断条件 fast ! null 会在一开始就发现 fast 是 null直接不进入循环然后 slow 就在 dummy 处执行 slow.next slow.next.next正好删除头节点。不需要任何额外的 if 分支。另一个让我记忆深刻的报错是返回值错误。当时我用一个变量 origHead 保存了原始 head最后 return origHead。测试用例里有一个“删除头节点”的场景执行之后链表已经变了但 origHead 仍然指向那个被删除的节点最后返回的结果自然是错的。从那以后我只要碰到链表删除类的问题无脑上虚拟头节点并且只返回 dummy.next这个坑就再也没踩过。5.2 优化执行时间的一些个人体会LeetCode 上这道题的运行时间不同语言和不同写法会有差别。Java 版本里有人用两次遍历跑了 0ms有人用双指针跑了 1ms这很正常。执行时间跟 LeetCode 服务器的波动、测试用例的规模都有关系不用太纠结那 1ms 的差异。关键是保证复杂度是 O(n)并且代码逻辑严谨就是一份好答案。我之前做过一个小型基准测试生成了 10 万个节点的链表分别用两次遍历和双指针各跑 100 遍结果是双指针确实更快大约快 10% 到 15%。原因也很好理解双指针遍历时快指针虽然走完了整个链表但慢指针只走了后半段总移动节点数大约为 L n 1而两次遍历的总移动节点数大约是 L (L - n)当 L 很大且 n 比较小时双指针的优势会更明显。当然这个差距在 LeetCode 上显示不出来但如果你在做性能敏感的项目这个细节是有意义的。5.3 常见问题速查表问题可能的原因解决办法空指针异常未判断 fast 是否为 null 就访问 fast.next使用虚拟头节点或者先判断 fast null删除的是头节点时结果错误最后返回了原 head没有使用 dummy.next统一返回 dummy.next删除的节点不对快指针先走步数写错应该走 n 或 n1对照推演过程检查循环次数循环陷入死循环while 条件写成 slow.next ! null 之类确认 fast 应该走到 null 还是最后一个节点内存相关错误C删除节点后没有 delete在 C 中确保释放被摘除节点的内存n 不合法非 LeetCode 场景未做参数校验增加防御性判断n 0 或 n 长度时直接返回5.4 一题多解从这道题延伸出去的其他思路除了两次遍历和双指针这道题其实还有其他思路可以探索。比如递归解法。递归本质上也是两次遍历的变体因为递归会先一路走到链表末尾然后在回溯的过程中计数。当回溯到第 n 个节点时执行删除操作。这种方式写出来代码很简洁但递归深度等于链表长度链表很长时比如上万节点可能会导致栈溢出所以我不太推荐在生产代码里用但用来拓展思路是好的。再比如用一个固定大小的“窗口”来模拟倒数查找。你可以维护一个长度为 n 的队列或者数组遍历链表的时候把节点塞进去满了就移除最前面的当链表遍历完队列里剩下的就是最后 n 个节点其中第一个就是要删除的。这个方法的本质是空间换时间空间复杂度 O(n)不如下面两种优秀但思路有趣。还有一种利用额外数组把所有节点存下来然后直接通过下标访问倒数第 n 个节点的前驱去做删除。这个方案的优点是查找直接、不容易出错但空间 O(n)不满足进阶要求。我一般拿这个方案来给初学者讲解“链表是物理结构、数组是逻辑索引”的概念差异但不建议作为面试答案。6. 变体题目与实战延伸6.1 删除倒数第 N 个节点的常见变体LeetCode 上有很多题目都可以看作这道题的变体或者用到这道题的技巧。题目本身上升一个难度就有“删除链表的倒数第 N 个节点”的可能变体要求不删除节点只是返回倒数第 N 个节点的值或者要求删除倒数第 N 到倒数第 M 之间的一段节点再或者链表是双向链表你怎么调整策略。每一种变体我都见过核心思路仍然不变找到目标位置处理好前驱和后继的指针关系。再往远处想判断一个链表是不是回文链表其中一个常见解法就是用快慢指针找到链表中点然后反转后半段进行比较。这里“找中点”的思路跟“找倒数第 N 个节点”的固定间距指针有些类似但又不完全一样。一个是快指针走两步慢指针走一步一个是快指针先走 n 步然后同速前进。如果你能把这几种快慢指针的不同形态分清楚链表这块的题你就能串起来了。6.2 面试中如何向面试官讲清你的思路面试遇到这道题我建议按这样的顺序表达先明确题目含义说清楚要删除倒数第 n 个节点接着提出最直观的方案——两次遍历然后自然过渡到优化——用双指针做到一次遍历最后补充边界条件的处理思路尤其用虚拟头节点统一删除逻辑。这样表达的好处是你展示了从暴力到优化的思考过程这正是面试官想看的。如果你上来直接背双指针代码面试官可能会追问你“为什么快指针要先走 n 1 步”一旦你对距离推导不够清楚就容易露馅。所以在那之前先把两次遍历和距离推导想明白比仅仅背会代码重要得多。我在带人的时候还喜欢让他们在白板上把链表画出来一步步走。看起来慢实际上特别有用。拿个简单的 1 - 2 - 3 - 4 - 5n 2画出 dummy、fast、slow 三个节点的移动轨迹比口头讲十遍都清楚。面试的时候如果允许你也可以在写代码之前先画一下示意面试官通常会很欣赏这种交流方式。6.3 从这道题抽象出的链表操作通用准则最后我想把这道题背后更通用的链表操作准则拎出来这比单纯记住这道题的解法更有价值。准则一任何链表删除操作优先考虑虚拟头节点。它能统一头节点和普通节点的删除逻辑减少分支判断提升代码的可读性和健壮性。准则二任何需要“倒数”概念的链表题优先想到双指针。固定间距的双指针就是“倒数”的天然映射它让查找倒数第 k 个节点这件事从“需要知道总长度”变成了“只需要一次遍历”。准则三任何时候修改链表的 next 指针都先确认当前节点的前驱关系。也就是你手里拿到的节点到底是要删除的节点、要返回的节点还是目标节点的前驱。很多链表 bug 的根源就是“手里拿错节点还对它做了错误的操作”。准则四循环条件一定要和“指针最终停在哪里”配套。你是希望 fast 停在 null 还是停在最后一个节点这决定了循环条件是 fast ! null 还是 fast.next ! null。搞混这两者是新手最容易犯的错误之一。最后再分享一个小技巧刷这道题的时候建议你把两次遍历、双指针、递归、数组辅助这四种方法都写一遍然后对同一个测试用例跑一遍观察各自的写法和思考方式。我个人在带过不少初学链表的朋友之后越来越觉得这道题堪称“链表题的基础缩影”它并不复杂但把链表的特性、边界、优化空间都浓缩到了一起。你把这道题吃透了后面很多链表题都会有豁然开朗的感觉。
