删除链表的倒数第 N 个结点是链表问题里被问得最多的一道题没有之一。它不像反转链表那样有一整套固定套路也不像合并两个有序链表那样一眼就能想到递归难点就藏在一个词上——“倒数”。链表只能从头往后走不能回头你没法像数组那样用下标倒着访问所以怎么在一次遍历里准确找到倒数第 N 个位置就成了核心问题。我见过很多基础不错的开发者能写出两次遍历的版本但一到快慢指针就容易搞混先走几步、循环里到底该判 fast 还是 fast.Next最后在边界条件上栽跟头。这篇文章不打算只贴一份能跑的代码我会把“为什么要用快慢指针”“为什么先走 N 步而不是 N-1 步”“哑结点到底解决了什么”这些关键问题逐个讲透。也整理了我在实际写代码和帮人 review 时经常遇到的几个典型错误每一个都有完整的定位过程。内容适合两类人一类是正在刷题准备面试的读者看完能把这题彻底吃透另一类是工作中需要手写链表操作的开发者搞清楚这些细节能帮你少走不少弯路。1. 这题为什么“看着简单写起来总差一步”1.1 题目到底在问什么先明确一下题目。输入是一个单链表的头结点 head和一个整数 n要求删除链表中倒数第 n 个结点并返回链表的头结点。比如链表是 1 → 2 → 3 → 4 → 5n 2那么倒数第二个结点是 4删除之后链表变成 1 → 2 → 3 → 5。题目的额外说明通常会带一句“n 保证是有效的”意思是 n 不会超过链表长度也不会小于 1。但实际写代码时我不建议完全依赖这个条件健壮性这种东西多防御一层总没坏处。很多人第一次做这题的最大困惑是链表的长度不知道我怎么知道哪个是倒数第 N 个这是一个非常合理的疑问。数组可以通过 length - N 直接定位链表不行它没有随机访问能力你只能从 head 开始一个一个地往后走。所以这题的本质其实是在“不知道总数”的前提下如何找到倒数的位置。有一个非常直观的类比想象一条单行道你站在这条路的最前面想找到从末尾数第 N 辆车。如果不知道这条路总共多长一个最简单的办法是先跑到路尽头数清楚总共有多少辆车然后重新从起点走走到“总数 - N 1”的位置。这就是两次遍历的思路也是大多数人能第一时间想到的解法。但还有更聪明的办法找两个朋友一个人先出发走 N 步停下来等你然后你们两个保持固定的 N 步距离一起往前走当前面那个人到达路尽头时你站的位置正好就是倒数第 N1 辆也就是被删除结点的前一个。1.2 为什么很多人第一次写会错这题的错误率相当高而且错法五花八门。最常见的几个fast 先走 N 步还是 N-1 步搞反。循环条件写成 fast.Next ! nil结果慢指针最终停的位置不对删错了结点。忘了用哑结点删除头结点时写一堆 if 分支最后还是漏了某种情况。返回的指针不是 dummy.Next而是原来的 head导致原头结点被删后返回了空引用。这些错误表面上看是“边界条件没处理好”实际上是对快慢指针工作过程的推导不够清晰。很多人只是背下了模板“fast 先走 N 步然后一起走”但没真正搞明白为什么这样做稍微换个条件就懵了。所以我建议这题一定要自己画一遍指针移动的过程或者至少在脑子里把每一步的位置推演清楚。理解了原理之后你会发现代码其实短得很而且不容易忘。2. 先把“倒数第N个”翻译成能计算的东西2.1 从链表长度出发的直观做法两次遍历的方案虽然不够“高级”但它是理解后面所有优化方案的基础。思路分两步第一次遍历计算链表长度 L第二次遍历找到第 L-N 个结点也就是待删除结点的前驱然后执行删除操作。举个例子。链表长度是 5要删除倒数第 2 个结点。L - N 5 - 2 3也就是说前驱是第 3 个结点从 1 开始计数即值为 3 的结点。删除它的后继也就是值为 4 的结点。这样理解起来非常直观倒数第 N 个结点正着数就是第 L - N 1 个它的前驱是第 L - N 个。注意一个细节如果链表长度 L 恰好等于 N那么要删除的就是头结点此时待删除结点没有前驱需要单独处理。两种处理方式一种是 if 判断后让 head head.Next另一种是前面加一个哑结点让所有情况统一走“删除某个结点的后继”这一条逻辑。第二种方式我后面会重点讲因为它是更多人选择的方案。2.2 两次遍历的代码和复杂度先给一份直观的 Python 实现方便你对照理解class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def removeNthFromEnd(head: Optional[ListNode], n: int) - Optional[ListNode]: # 第一次遍历计算链表长度 length 0 cur head while cur: length 1 cur cur.next # 要删除结点的前驱正着数是第 length - n 个 # 引入哑结点把删除头结点的特殊情况统一掉 dummy ListNode(0, head) cur dummy for _ in range(length - n): cur cur.next # cur 现在指向待删除结点的前驱 cur.next cur.next.next return dummy.next这里有一个很多新手容易忽略的点为什么循环次数是 length - n 而不是 length - n 1因为我们要找的是“前驱”的位置。前驱是第 L - N 个结点而 dummy 是第 0 个结点所以要往前移动 L - N 步才能从 dummy 到达前驱。你可以用刚才的例子验证L 5N 2前驱是第 3 个结点从 dummy 走 3 步到达循环次数正好是 length - n 3。时间复杂度是 O(L)空间复杂度是 O(1)。这里 O(1) 指的是不依赖链表长度的额外空间只用了几个指针变量。2.3 两次遍历方案的问题在哪两次遍历方案最大的问题不是慢而是“多了一次遍历”。如果题目没有明确限制这个方案其实完全可接受O(2L) 和 O(L) 在渐进复杂度上是同一个量级。但很多面试官会追问能不能只遍历一次我自己的感受是这个追问与其说是在考察算法优化不如说是在考察你对“双指针模型”的敏感度。链表题里凡是遇到“倒数”“环”“中点”这些词第一时间就该想到快慢指针。两次遍历方案相当于先探测了整个链表而一次遍历方案则通过两个指针的错位把“倒数”转换成“正数相差 N”的相对距离问题不需要预知链表长度。所以下面要讲的快慢指针方案不只是一个更优解更是一种思维模式的转变当信息不足时用两个指针制造“时间差”或“距离差”来弥补。3. 快慢指针一次遍历解决的完整推导3.1 快慢指针的距离设定快慢指针的基本思路是定义 slow 和 fast 两个指针初始都指向 dummy 结点。fast 先走 N 步此时 fast 和 slow 之间的距离是 N。然后 slow 和 fast 同步向后移动每次各走一步直到 fast 到达链表末尾也就是 fast 变成 null。这时slow 所在的位置恰好是倒数第 N1 个结点也就是待删除结点的前驱。让 slow.next slow.next.next删除完成。为什么是倒数第 N1 个因为 fast 先走了 N 步又和 slow 一起走到了链表末尾。整个过程中 fast 始终比 slow 快 N 个结点。当 fast 到达链表的 null 位置时slow 距离末尾也是 N 个结点也就是说 slow 的位置是倒数第 N1 位。前驱找到了删除后继就是顺理成章的事。这里关键是理解 null 是算作一个位置的。fast 到达 null 时如果原来链表长度为 Lfast 一共走了 L1 步从 dummy 出发的话。而 slow 走了 L1-N 步距离 null 还有 N 个位置所以是倒数第 N1 个有效结点。3.2 为什么先走N步而不是N-1步这是整个算法里最容易搞混的地方。先说结论fast 先走 N 步而不是 N-1 步是因为我们要找的是被删除结点的“前驱”而不是被删除结点本身。如果 fast 先走 N-1 步那么当 fast 到达链表最后一个有效结点时fast 和 slow 之间的距离是 N-1slow 恰好停在倒数第 N 个结点上也就是要被删除的结点。此时你虽然找到了目标结点但单链表无法通过自身拿到前驱你没法把前一个结点的 next 指向它的后继删除操作做不了除非再维护一个 prev 指针。这样也不是不行但逻辑上绕了一圈代码更容易出错。而 fast 先走 N 步slow 停在倒数第 N1 个结点恰好是前驱位置直接更新 next 指针就能完成删除。这是“删除单链表某个结点必须先拿到前驱”这一特性的直接体现也是这个方案最优雅的地方。再做个对比记忆如果题目改成“返回倒数第 N 个结点”那 fast 先走 N-1 步如果题目是“删除倒数第 N 个结点”那 fast 先走 N 步。两者差一步就是因为“找结点”和“找前驱”是两个不同的目标。3.3 慢指针的位置推导用具体例子推导一遍。链表 1 → 2 → 3 → 4 → 5dummy 在开头N2。初始dummy → 1 → 2 → 3 → 4 → 5 → nullfast 和 slow 都在 dummy。fast 先走 2 步fast 从 dummy → 1 → 2此时 slow 还在 dummy。fast 和 slow 一起走。fast 从 2 → 3 → 4 → 5 → null一共走 3 步到 null。slow 也跟着走 3 步dummy → 1 → 2 → 3。此时 slow 停在值为 3 的结点上即倒数第 3 个结点从后往前数5 是倒数第 14 是倒数第 23 是倒数第 3。4 是倒数第 2正是要删除的结点。slow.next slow.next.next 就把 4 删掉了。在这个例子里链表长度是 5要删除倒数第 2 个slow 停在前驱也就是正数第 3 个。泛化到任意长度 Lslow 走的总步数是 L1-N从 dummy 算起正好对应倒数第 N1 个结点。这个推导每一步都清晰可见所以不建议背模板强烈建议自己画一遍。4. 哑结点把边界情况变成普通情况4.1 没有哑结点时删除头结点有多麻烦先假设不用哑结点快慢指针都从 head 开始。还是链表 1 → 2 → 3 → 4 → 5假设 n 5也就是要删除倒数第 5 个即头结点 1。fast 先走 5 步会发现走到链表末尾的 null此时 slow 还停在 head。fast 已经变成 null 了所以不会进入“fast 非空时同时移动”的循环。这个时候你面临的局面是slow 指向头结点而头结点恰好是待删除结点但它没有前驱。你要么单独写一句 head head.next要么就得用法图省事的方式。这就是没有哑结点时的典型尴尬绝大多数情况可以走通用逻辑唯独要删除头结点时必须开一个特判分支。代码多了一条 if 不算什么真正的问题是特判逻辑在后续维护时很容易被忽略。尤其当这段代码被封装成工具函数、被不同的人反复修改时他们通常会假定“函数内部统一处理了所有情况”结果一改就出 bug。4.2 有哑结点后的事故现场变成一根指针的事哑结点的做法是在真正的头结点前再加一个虚拟结点 dummy让 dummy.next head然后只操作这个新链表。因为 dummy 本身不会被删除所以“删除倒数第 N 个”在加了 dummy 的链表里永远都有一个前驱特殊分支消失了。还是刚才的例子n 5链表演变成 dummy → 1 → 2 → 3 → 4 → 5。fast 先走 5 步dummy → 1 → 2 → 3 → 4 → 5 → null。此时 fast 为 nullslow 还在 dummy。slow.next 指向的 1 就是待删除结点执行 slow.next slow.next.next链表变成 dummy → 2 → 3 → 4 → 5。最后返回 dummy.next即 2。整个过程没有任何 if 分支逻辑完全统一。这种做法本质上是用“增加一个虚拟结点”换来了“统一的操作模型”。我在写链表相关代码时几乎所有涉及位置删除、区间操作的场景都会先加一个 dummy不是为了“炫技”而是为了少写条件分支降低心智负担。人在写代码时犯错最多的位置就是 if 分支能砍掉一个是一个。4.3 什么时候可以考虑不用哑结点哑结点不是银弹。它引入了一个额外的空结点虽然大多数时候无伤大雅但如果你的代码环境极其在意空间比如嵌入式开发里链表结点内存非常宝贵dummy 这一步就会让你多分配一个结点的空间。不过在实际工程里为了统一逻辑而多一个临时结点代价完全可以接受大多数场景我都推荐使用。另一种情况是你只是做题、写算法验证思路而且明确知道自己不会处理删除头结点这种边界比如 n 一定小于链表长度。这时不用 dummy 也能跑通代码还能少几行。但请注意真实面试里不要赌“面试官不会测头结点删除”这是最常考的边界没有之一。保险起见我都会加上 dummy一份代码覆盖全部 case省得临场补漏。5. 可直接抄的完整实现5.1 Python 版本Python 写链表题最舒服的是不用考虑内存释放直接切引用就行class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def removeNthFromEnd(head: Optional[ListNode], n: int) - Optional[ListNode]: dummy ListNode(0, head) fast dummy slow dummy # fast 先走 n 步 for _ in range(n): fast fast.next # 同步移动直到 fast 到达末尾 null while fast: fast fast.next slow slow.next # 此时 slow 指向待删除结点的前驱 slow.next slow.next.next return dummy.next细心的读者会发现fast 一共走了 N 步。如果 N 等于链表长度fast 走完之后正好是 nullwhile 循环根本不会执行slow 还停在 dummyslow.next 就是头结点直接删除符合预期。这正好验证了第 4 章说的“哑结点统一处理边界”。5.2 Go 版本Go 的链表常见写法是用结构体指针代码结构上跟 Python 很像type ListNode struct { Val int Next *ListNode } func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy : ListNode{Val: 0, Next: head} fast, slow : dummy, dummy for i : 0; i n; i { fast fast.Next } for fast ! nil { fast fast.Next slow slow.Next } slow.Next slow.Next.Next return dummy.Next }Go 里有个小细节for fast ! nil与for fast等价但 Go 的编译器会提醒你把条件写完整所以这里用for fast ! nil更符合 Go 的习惯。另外如果你是在 LeetCode 这类在线平台上写ListNode结构体通常已经给好了不需要自己声明。5.3 Java 版本与内存释放细节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 ! null) { fast fast.next; slow slow.next; } slow.next slow.next.next; return dummy.next; }在 Java 里被删除的结点如果没有其他引用指向它会被 GC 自动回收你不用手动管。但如果你用 C 做同样的操作那么删除结点的同时要记得delete这个结点。不然会发生什么内存泄漏。尤其链表题刷多了以后很多人会把精力放在指针移动上忘了释放这一层。我的习惯是先把被删结点存到一个临时变量里然后跳链最后释放临时变量。改成 C 大概是ListNode* tmp slow-next; slow-next slow-next-next; delete tmp;这三行顺序不能乱。先把后继摘掉再释放结点否则一旦释放了你再访问它的 next 就是未定义行为。6. 我实际跑代码时踩过的坑6.1 一个空指针引发的思考第一次用快慢指针写这题时我的代码长这样def removeNthFromEnd(head, n): fast head slow head for _ in range(n): fast fast.next while fast.next: fast fast.next slow slow.next slow.next slow.next.next return head看起来很像模板吧问题就出在循环条件fast.next。思考一下当 n 等于链表长度时比如链表只有 1 个结点n 1fast 先走 1 步就变成了 null然后执行while fast.next时系统直接崩了——你在对一个 null 取 next 属性这就是空指针异常。跑测试时这一条用例直接红而且报错信息不会告诉你“你该用 while fast”它只会说 null 对象没有 next 属性得花时间排查。我从这个坑里总结出两条规律。第一凡是涉及 fast 走到链表末尾后会变成 null 的逻辑循环条件尽量用while fast而不是while fast.next。第二如果必须用fast.next你得先确保 fast 不可能为 null或者在一开始就单独处理 n 长度的场景。很多人的代码里为什么又要特判又要分叉就是因为循环条件选择不当导致的连锁反应。6.2 循环条件写错导致多删一个另一个常见错误是很多人知道不能用fast.next于是改成while slow.next ! fast.next之类的花式写法。这种写法不是不能跑但很容易在循环结束条件上出偏差结果多移动了一步最后删除的结点变成了倒数第 N-1 个。有一次我 review 别人的代码看到他把同步移动的循环写成了while fast.next ! None: fast fast.next slow slow.next他加了一个fast.next ! None而不是fast ! None。单独看这段逻辑它的意思是“fast 走到最后一个有效结点就停”此时 slow 还没走到位于是他又在外面手动补了一步 slow slow.next。一来二去代码里出现了多余的魔法步数如果 N 特别大或者链表特别短这种手工补步很容易错。所以我一直跟合作的人强调这类两道指针同步移动的题目循环判断条件只用跟随的那个指针本身不要玩花活。6.3 返回了错误的头结点如果你加了 dummy最后返回的是dummy.next这是标准答案。但如果你图省事把head单独存了一个变量最后 return head问题就来了。考虑链表只有一个结点n 1。dummy → 结点A → null。fast 走 1 步到 nullslow 不动slow.next slow.next.next 之后dummy.next 变成 null。此时你手头那个 head 变量还指着结点A但结点A已经不在链表里了。如果你 return head返回的是一个已经被删除的孤立结点头测试直接失败。这个错误太容易发生了因为它藏在“变量仍然指向旧对象”这个隐蔽细节里。很多时候我们觉得 head 是链表的“根”下意识就要返回它但在这个操作里头结点可能已经被删除了只有 dummy 才知道谁才是新的头。这也解释了为什么我在所有操作链表的工具函数里都坚持用 dummy返回值的正确性由它保证而不是靠人记得手动更新 head。7. 从这题延伸出去快慢指针的更多用法7.1 找链表中间结点快慢指针最经典的另一个应用是找链表的中间结点。fast 每次走两步slow 每次走一步当 fast 到达末尾时slow 就在中间位置。这个思路和“删除倒数第 N 个”的距离设定本质一样只是步长从“先走 N 步再同步走”变成了“永远保持两倍速”。有一个细节值得注意链表长度是偶数时中间结点有两个候选题目到底返回哪个取决于你循环条件用fast ! nil还是fast.next ! nil。这个坑和删除倒数第 N 个的循环条件坑一模一样。如果你弄懂了刚才分析的fast nil与fast.next nil的区别这里的偶数情况就不会懵。7.2 判断链表是否有环判断链表是否有环也是快慢指针的标准应用fast 走两步slow 走一步如果链表有环两者必定相遇。这个算法的正确性可以用“速度差”来解释如果环存在可以看作 slow 停在原地fast 以每步 1 个单位的速度逼近它最终一定会追上。这个模型的本质和“删除倒数第 N 个”完全一样只是速度比从“速度相同、开始位置差 N”变成了“开始位置相同、速度差一倍”。理解了这两种差值模型你就掌握了快慢指针的大部分使用场景。7.3 删除中间结点等其他变体LeetCode 上还有一道“删除链表的中间结点”的题解法是先用快慢指针找到中间前驱然后删掉后继。代码逻辑和本文主题高度相似唯一区别是“n 是多少”不再由输入给定而是先通过快慢指针探测出来。还有一类题是“删除重复元素”虽然不直接用快慢指针但对“前驱-后继”指针操作的熟练度要求同样很高。我的建议是把删除倒数第 N 个结点当作链表操作题的“元模型”来刷。它包含了三个最核心的要素哑结点处理边界、快慢指针错位、前驱删除操作。这三个要素在后续大量的链表题里会反复出现。你现在把这题吃透等于一次性把这三件套全部练到位了。最后再分享一个自己的习惯做链表题时我不会直接在内存里空想而是先在草稿纸上画几个格子表示结点再用两个小方块表示指针一步步推演到结束。这个练习看似繁琐但它能非常有效地帮你构建指针移动的直觉尤其是面对删除倒数第 N 个结点这类需要精确控制“差一步”的题目。推演过几轮之后你会发现快慢指针不再是模板而是一套真正属于自己的思维方式。