删除链表的倒数第 N 个结点这道题我在面试里遇到过也在实际工程里亲手写过。你可能觉得它简单就是“先数长度再删”但真正写对的人不多——尤其当 N 正好等于链表长度、或者链表只有一个结点的时候十个人里有六七个会翻车。这篇文章就把这道题彻底拆开从最朴素的两次遍历讲到双指针一次遍历再带你过一遍边界条件、代码实现、自测用例和面试扩展争取看完之后你能闭着眼睛把代码写对。1. 项目概述与核心需求解析1.1 题面是什么这是面试里最常见的链表操作之一给你一个单链表要求删除链表的倒数第 N 个结点并返回链表的头结点。常见定义如下struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };输入示例链表1 - 2 - 3 - 4 - 5N 2删除倒数第 2 个结点也就是值为 4 的结点输出变成1 - 2 - 3 - 5。听起来很清晰对吧但这里有个暗坑“倒数第 N 个结点”是从尾节点开始往头数第 1 个是尾结点本身。很多人写代码时容易把“倒数第 N”和“正数第 len - N”搞混一步错步步错。1.2 为什么不直接拿长度来算难点到底在哪链表和数组最大的区别是数组支持随机访问你知道 index 就能 O(1) 拿到元素链表只能从头结点开始一个一个 next 走。要删除倒数第 N 个结点你至少要知道“目标结点的前驱是谁”因为删除操作本质上是让prev-next target-next。可问题是单链表没有指向前驱的指针你没法从尾往头走。这就要么先遍历一遍拿到总长度算出正数位置再遍历第二遍找到前驱要么用两个指针维护一个固定距离的“窗口”一次遍历做到同样效果。两种方案各有各的使用场景但双指针解法在工程面试中通常更受青睐因为它体现出了你对“链表的遍历特性”有没有真正理解。另外题目的 N 有一个明确约束1 N 链长。也就是说 N 不会比链表长度更大但你依然要考虑 N 正好等于链长的情况——这时要删的是头结点处理不好就直接返回了空链表或者丢失头结点位置。很多人挂就挂在这一条上。2. 算法思路与设计拆解2.1 最容易想到的两次遍历方案先数长度再找前驱一次最简单、最不会出错的逻辑是遍历一次链表统计结点总数len。计算目标结点的正数位置pos len - N 1从 1 开始数。找到第pos - 1个结点作为前驱把它next指向pos 1的结点。如果pos 1说明删除头结点直接返回头结点的next。这个方案为什么适合先讲因为它零难度、直观、不容易写出野指针。但它要遍历两次链表时间复杂度是 O(2n) 也就是 O(n)空间复杂度 O(1)性能上完全够用。真正的问题是如果链表很长、或者这个操作被高频调用两次遍历就会浪费一次全量 IO。在工程里链表结点可能不是内存里的简单对象而是数据库记录映射或者网络传输的序列化节点多遍历一次的成本会肉眼可见地放大。因此大多数面试官会在你给出两次遍历后追问一句“能不能只遍历一次”这就引入了双指针解法。2.2 双指针一次遍历快慢指针的由来双指针的核心思想非常朴素既然我们想找“离尾部距离为 N”的结点那就让两个指针中间间隔 N 个结点然后同步往后走。当快指针到达链表末尾null慢指针恰好停在倒数第 N 个结点上。具体操作让快指针fast先走 N 步。然后让慢指针slow从头结点出发和fast一起每次走一步。当fast走到 null 时slow的位置正好是倒数第 N 个结点。等等这里要仔细想如果我们只是要找到“倒数第 N 个结点”上述逻辑是正确的。但删除操作需要知道的是“倒数第 N 个结点的前驱”。所以更稳妥的做法是让快指针先走 N1 步然后再让慢指针和快指针同步前进。这样当fast到 null 时slow正好指向倒数第 N1 个结点也就是目标结点的前驱。或者你也可以这样理解快指针先走 N 步然后慢指针指向头结点的前一个位置虚拟头节点两者同步走一步最后慢指针落在前驱上。这两种描述本质上是一样的只是代码上的表达略有不同。我在面试时更推荐用“虚拟头节点 快指针先走 N1 步”的写法因为它把“删头结点”这个特殊情况直接吸收掉了不用写额外的 if 判断。2.3 虚拟头节点的妙用避免“删头”特判什么是虚拟头节点就是创建一个额外的结点dummy它的next指向原链表的头结点。无论原链表是空还是只有一个结点dummy永远作为新的“头结点”参与逻辑。最后返回时我们返回dummy-next而不是原来的head。这样有什么好处如果删除的是头结点在两次遍历方案里你需要单独处理return head-next在虚拟头节点方案里删除逻辑完全统一因为头结点也有前驱了就是dummy。链表的边界处理少一个分支代码不容易漏。即使原链表为空虽然题目约束 N 不小于 1但工程中可能传入空链表dummy也能保证指针操作安全。虚拟头节点是链表类题目里极其常用的技巧不是这道题专属。凡是涉及“可能删除第一个结点”的题目比如删除指定值、删除重复结点我都会无脑加一个dummy。这不是代码洁癖而是从根上消灭一类空指针 bug。3. 完整实现与代码细节3.1 不同语言的核心实现用双指针加虚拟头节点Python 写出来是这样的class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def removeNthFromEnd(head: ListNode, n: int) - ListNode: dummy ListNode(0, head) fast dummy slow dummy # 快指针先走 n 步此时 fast 指向第 n 个结点 for _ in range(n): fast fast.next # 然后让 slow 和 fast 一起走直到 fast 到 null # 因为 fast 是从 dummy 出发先走了 n 步再起点相同所以 fast 走到 null 时 # slow 指向倒数第 n 个结点的前驱 while fast.next: fast fast.next slow slow.next # slow.next 就是要删除的结点 slow.next slow.next.next return dummy.next这里我解释一下为什么快指针先走 n 步而不是 n1 步。因为快指针是从dummy出发的dummy本来就在头结点前面。先走 n 步快指针正好走到正数第 n 个结点头结点算第 1 个。然后while fast.next循环的意思是只要快指针后面还有结点就一起走。当循环结束时快指针指向最后一个结点而非 null。此时慢指针指向倒数第 n1 个结点也就是目标结点的前驱。这和我前面说的“快指针先走 n1 步再走到 null”的写法是等价的只是终止条件不同。C 实现完全同理class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); ListNode* fast dummy; ListNode* slow dummy; while (n--) { fast fast-next; } while (fast-next) { fast fast-next; slow slow-next; } ListNode* toDelete slow-next; slow-next slow-next-next; delete toDelete; // 工程中记得释放内存面试时如果环境支持也可以不写 return dummy-next; } };Java 版本public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode fast dummy; ListNode slow dummy; for (int i 0; i n; i) { fast fast.next; } while (fast.next ! null) { fast fast.next; slow slow.next; } slow.next slow.next.next; return dummy.next; }三种语言逻辑完全一致。你只要理解了“快指针从 dummy 出发先走 n 步然后同步走直到快指针到达尾节点慢指针即位于倒数第 n1 个结点”代码就不会写错。3.2 边界条件与关键判断这道题表面是算法题实际考的是你对链表指针边界的敏感度。关键边界有三个边界一N 等于链表长度。此时要删除的是头结点。虚拟头节点方案下慢指针最后会停在 dummy执行slow.next slow.next.next后dummy.next 指向原来的第二个结点结果完全正确。如果你没有用 dummy而是直接让 fast 先走 n 步、slow 从 head 出发最后 slow 会指向 head即要删的结点你需要额外判断并返回head.next容易漏。边界二链表只有一个结点且 N 1。这是“N 等于链长”的特殊情况。删除后链表为空。dummy 方案返回null正确。非 dummy 方案则必须先记录新头否则头结点删除后你就拿不到链表了。边界三快指针的while条件。我用的是while (fast-next)也就是快指针停在最后一个结点。如果你写的是while (fast)那么快指针最终会变成 nullptr此时慢指针会比预期多走一步指向要删除的结点了。两种写法对应的“快指针先走 n 步还是 n1 步”是不同的千万别混。3.3 复杂度分析与内存细节时间复杂度O(L)其中 L 是链表长度。两次遍历方案是 O(2L)双指针是 O(L)常数差异在数据量小时几乎无感但双指针更优雅。空间复杂度O(1)只用了两个额外指针加一个 dummy 结点。这里有个容易被忽视的内存细节在 C/C 中如果slow-next是需要被删除的结点删除后应该把它delete释放掉。否则工程里就会有内存泄漏。但在 LeetCode 这类评测环境里判题机自己管理内存不 delete 也不影响结果。我平时写工程代码会释放面试写题则看情况如果面试官明确说“不考虑内存释放”就简洁为主。另外有些人写“双指针”时会真正创建两个独立的链表节点这完全没有必要。指针本身是轻量级变量遍历过程中改变它的指向即可。不需要复制链表更不需要额外分配数组。如果面试时你在那儿new了好几个 ListNode面试官会觉得你理解跑偏了。4. 实操过程从画图到调试4.1 用例子一步步推演纸上谈兵不如实跑一遍。我们以链表1 - 2 - 3 - 4 - 5N 2 为例走一遍双指针流程。初始状态dummy - 1 - 2 - 3 - 4 - 5 - nullptr fast dummy slow dummy第一步快指针先走 2 步。此时fast 2 的结点 slow dummy第二步进入while(fast-next)循环。这里要清楚每次循环 fast 和 slow 都同时前进一步。状态0fast 指向 2fast-next 是 3非空进入循环。循环后 fast 指向 3slow 指向 1。状态1fast 指向 3fast-next 是 4非空进入循环。循环后 fast 指向 4slow 指向 2。状态2fast 指向 4fast-next 是 5非空进入循环。循环后 fast 指向 5slow 指向 3。状态3fast 指向 5fast-next 是 nullptr循环结束。此时 slow 指向 3slow-next 指向 4正是我们要删除的倒数第 2 个结点。执行slow-next slow-next-next链表变成dummy - 1 - 2 - 3 - 5 - nullptr返回dummy-next得到头结点 1。完美。如果你把 N 换成 5也就是删除倒数第 5 个结点头结点推演如下fast 开始从 dummy 走 5 步最终 fast 指向 5最后一个结点slow 始终是 dummy。进入 while 循环时fast-next为 nullptr循环一次都不执行。slow-next slow-next-next把 dummy 后面的 1 删除返回 dummy-next 即原来的 2。结果链表2 - 3 - 4 - 5。正确。4.2 常见错误与坑指针偏移、空指针、N 等于链长我自己写这道题时踩过几个坑也帮人 review 过不少类似代码最常见的错误大概是这四类。第一类先走 n-1 步导致删除错位。有人觉得“倒数第 N 个”那快指针就比慢指针领先 N-1 个位置。这种想法在“找倒数第 N 个结点”的题目里是对的但删除前驱需要“领先 N 个位置”。差一步最后删除的就会变成倒数第 N1 个结点。第二类while 条件写错。用while(fast)代替while(fast-next)导致快指针越过尾节点为 nullptr慢指针继续向前多走了一步。后果是删除的不是目标前驱而是目标本身或者更危险的是slow-next为 nullptr接着访问slow-next-next直接空指针崩溃。第三类没有使用 dummy又忘了处理“删除头结点”的情况。很多人第一次写两次遍历版本时都这么翻车过。先数长度 len 5N 5计算正数位置 pos 1然后去找第 0 个结点“前驱”——根本没有前驱这时如果不写 if 特判代码就访问非法内存了。第四类误以为 N 从 0 开始。题目明确说 N 从 1 开始但和数组下标习惯混了之后偶尔会把 n 减一导致结果偏一位。我会建议代码里刻意写注释// N is 1-based, so fast goes n steps。4.3 如何快速自测几组必测用例我在写完代码后一般会准备一组针对边界的小用例每次都跑一遍。这道题我固定测五组用例链表N期望输出目的11-2-3-4-521-2-3-5常规删除211null唯一结点删掉31-222删除头结点41-211删除尾结点51-2-332-3N 等于链长且长度大于1如果一组代码能把这五组全部跑对基本就没有明显的边界问题了。另外建议再补一个稍长的链表例如 1 到 100随机选 N 跑一遍并对照两次遍历版本的结果是否一致。这样能同时验证普通情况和边界情况。5. 常见问题与排查技巧实录5.1 为什么快指针先走 N 步而不是 N-1 步这是评论区问得最多的问题。我换一种方式解释快慢指针之间差多少步取决于你最终希望 slow 停在哪里。如果目标是“找到倒数第 N 个结点”那么快指针领先 N-1 步同步走当快指针到 null 时慢指针就在倒数第 N 个结点上。如果目标是“删除倒数第 N 个结点”你需要找到它的前驱也就是倒数第 N1 个结点。那么快指针需要领先 N 步。为什么因为从倒数第 N1 个结点到链表末尾null的距离恰好比从倒数第 N 个结点到末尾的距离多 1。领先 N 步慢指针就会在快指针到 null 前一步停在目标前驱上。用同样的逻辑可以推导出“快指针从 dummy 出发先走 N 步然后 while(fast-next) 循环slow 停在倒数第 N1 个结点”。这个推导过程比背代码重要得多面试时你能画图说出来比直接报答案有价值。5.2 不用虚拟头节点怎么写有的面试官可能会说“不要用 dummy自己处理特殊情况”这时候也会有简洁写法def removeNthFromEnd(head, n): fast head slow head for _ in range(n): fast fast.next if fast is None: return head.next while fast.next: fast fast.next slow slow.next slow.next slow.next.next return head这里的区别是先让 fast 从头结点走 n 步如果 fast 已经是 None说明 N 等于链长删除的是头结点直接返回head.next。如果 fast 不为 None再让 slow 从头走while fast.next结束后 slow 指向目标前驱。这个写法少一个 dummy 结点但多一个 if 分支二者都能通过。我自己的观点是只要你逻辑清楚用不用 dummy 都行但如果你刚开始练建议先掌握 dummy 版本它能覆盖更多边界条件思路更统一。5.3 其他解法递归、栈、链表反转双指针不是唯一解法面试中还有人提到三种替代思路。递归解法。利用递归返回时的“回溯次数”来定位倒数位置。递归函数先走到链表末尾回溯时计数器加一当计数器等于 N1 时说明当前结点是目标前驱修改其 next。不过递归会使用 O(L) 的栈空间在链表很长的时候有栈溢出风险。建议作为思路拓展不作为主推方案。栈解法。将链表结点依次压栈然后弹出 N 个此时栈顶就是要删除结点的前驱。思路很简单但额外空间 O(L)。栈解法在处理“倒数第 K”问题时比较通用但如果只删除一个结点明显不如双指针省空间。链表反转解法。先把链表反转变成“正数第 N 个结点的前驱”删完后反转回来。这个思路可行但需要三次遍历且修改了原链表结构。除非题目要求你“不许用双指针、不许用额外空间、只能动指针”否则我不推荐。这些解法的价值在于帮助你理解链表操作的多样性。面试时你能说出双指针之外还有哪些路子并说明各自复杂度会显得基础很扎实。5.4 面试扩展一次遍历求中间结点/判断环这道题最常被延伸出的变体是“寻找链表的中间结点”和“判断链表是否有环”。它们都能用快慢指针解决只是快指针的步伐不一样。寻找中间结点快指针每次走两步慢指针每次走一步。快指针到末尾时慢指针恰好在中间。链表长度奇偶数会在中间位置有细微差异LeetCode 有专门题目解法基本一致。判断有环快指针每次走两步慢指针每次走一步。如果快指针遇到 null说明无环如果快慢指针相遇说明有环。这就是 Floyd 判圈算法核心思想是相对速度差为 1只要在圈内迟早能追上。寻找环的入口相遇后把快指针重置到头结点然后快慢指针都每次走一步再次相遇点就是环的入口。原理涉及 Floyd 算法的数学推导和链表删除题的思路有点远但都属于“快慢指针家族”。有了删除倒数第 N 个结点的基础你去理解其它快慢指针问题会轻松很多因为核心都是“两个指针一个跑得快一个跑得慢利用步伐差建立位置关系”。5.5 我用这份思路解决的一次真实线上问题说来也挺有意思我前阵子负责的一个老服务里有个内存缓存队列是单链表实现的定时任务要清理“倒数第 10 个”超时任务。原本代码是用数组存下所有节点地址然后按下标删性能很差。我顺手改成双指针一次遍历就把目标节点找出来。改完后处理耗时从平均 8ms 降到了 2ms 左右。当然生产环境里如果频繁增删头部我会建议直接用双向链表或者 GC 语言内置的 List 结构没必要手动造轮子。但如果你使用 C/C 或者需要精确控制内存池手写链表时“删除倒数第 N 个结点”这个双指针模型是很实用的基础组件。它能让你在不引入额外存储的情况下用一次遍历完成目标定位这在 IO 开销大的场景里收益很明显。最后说一点个人体会。链表题最怕的不是写不出来而是“好像写出来了但说不清楚为什么”。我见过很多人能把双指针代码背得滚瓜烂熟但换一个 N 的定义、加一个 dummy、或者要求返回被删除结点本身立刻就乱。真正的掌握标准是你能在白板上画出让 fast 先走 n 步的指针轨迹能解释清楚为什么循环条件要用fast-next而不是fast能写满五组边界测试用例。如果这篇文章能帮你在下次遇到这道题时多一分从容那我这几个小时就没白打字。