前阵子帮朋友做模拟面试轮到他手撕链表题抽到的就是LeetCode第19题删除链表的倒数第N个结点。他第一反应是两次遍历先数长度再走一遍删节点。这个方案没问题但面试官追问了一句“能不能一次遍历”他卡住了。这道题就是这样看起来简单实则把链表的遍历、指针操纵、边界处理全串起来了刷题群里几乎天天有人问。无论你是刚开始刷LeetCode还是准备一二线大厂算法面试这道题都值得花时间吃透。今天我把双指针、栈辅助、递归、两次遍历几种主流思路全部拆开讲一遍顺带分享我自己写代码时踩过的坑和测试技巧。1. 先看懂题目在问什么1.1 题目要求一句话理解LeetCode第19题的描述非常短给你一个单链表的头结点 head以及一个整数 n删除链表的倒数第 n 个结点并返回链表的头结点。比如链表是1 - 2 - 3 - 4 - 5n 2倒数第2个结点是4删除后变成1 - 2 - 3 - 5。这里有几个核心点需要先锚定住。单链表的特点是只能从 head 开始往后走没法从尾部倒着访问所以“倒数第 n 个”天然是个不好直接处理的位置。题目没有给链表长度意味着你不能靠长度公式定位必须先要知道长度或者用其他技巧。最后还要注意删除的是“结点”本身而不是值这意味着必须操作前驱结点的 next 指针而不是单纯改 val。很多新手在这里翻车以为找到目标节点改值就行实际上链表删除的本质是绕过目标节点让前驱的 next 直接指向后继。1.2 为什么这道题值得刷三遍这道题之所以在LeetCode上热度高不只是因为它是经典面试题更因为它用极短的问题覆盖了链表操作里几乎所有关键难点。第一遍刷重点是建立“删除链表节点需要找前驱”的意识第二遍刷重点理解双指针中快指针先走 n 步的几何意义第三遍刷可以在面试场景里从容地把两次遍历、栈、双指针三种方案按复杂度递进讲出来。我自己面试候选人的时候常拿这道题当热身题因为从一个人怎么处理边界条件基本能看出他对链表的理解深度。很多人能把 main case 写出来但一遇到“链表只有一个节点删除后 head 会变成 null”就懵了。这种细节恰恰是面试官最喜欢追问的地方也是刷题笔记里最该记的东西。2. 双指针法一次遍历就能删2.1 快慢指针的核心逻辑双指针法是这道题最推荐的解法也是最常被面试官期待的答案。它的核心是制造一个“固定的间隔”让两个指针在同一时刻只有一个指向目标节点位置。具体做法是初始化两个指针 slow 和 fast都从虚拟头结点出发。fast 先移动 n 步然后 slow 和 fast 一起同步移动直到 fast 走到链表末尾的 null 位置。此时 slow 停在哪里正好停在倒数第 n 个结点的前驱即倒数第 n1 个结点。于是可以直接执行slow.next slow.next.next完成删除。为什么 fast 先走 n 步而不是 n-1 步这直接关系到 slow 停靠位置的公式。如果 fast 一开始也指向虚拟头结点走 n 步后fast 和 slow 之间相隔 n 个结点。当 fast 到达 null 时slow 落后 n 个位置所以 slow 指向的正是倒数第 n1 个结点。如果先走 n-1 步fast 最后停在最后一个结点而不是 null那 slow 就会指到倒数第 n 个结点本身——这反而没法删因为你没有前驱。这是二分容易搞混的地方建议在纸上画一遍。2.2 虚拟头结点的作用很多初学者写链表删除题时会漏掉一个细节如果删的是头结点怎么办比如链表是[1]n 1要删掉唯一节点删除后链表应该为空返回值是 null。如果不加虚拟头结点普通逻辑会写成head.next head.next.next但 head 已经是要删的目标了这行代码会直接空指针或者需要额外写一个if (slow head)的分支。挺烦的。解决办法是在链表头部前面加一个 dummy 节点让 dummy.next 指向原来的 head。这个 dummy 节点不参与业务逻辑纯粹是为了让头结点的删除操作和普通节点统一起来。这样 slow 和 fast 都从 dummy 出发即使删除的是原链表的头结点slow 也始终有前驱可以操作。最后返回dummy.next既兼顾了安全又让代码变得干净。LeetCode 的链表题基本都建议用这个套路不只是这一题凡是涉及删除或可能改变头结点的题目都要优先想到加虚拟头。2.3 为什么尾指针停在倒数第 N1 个结点如果你还是有点晕我们做一个纯数学推导。假设链表长度为 L虚拟头结点位置记为第0个位置。fast 先走 n 步此时 fast 位于第 n 个位置。接着让 slow 和 fast 以相同速度移动当 fast 走到 null 时fast 移动了总共 L - n 1 步因为从虚拟头到 null 距离是 L1减去已经先走的 n 步。slow 同样移动了 L - n 1 步于是 slow 位于位置 L - n 1。原链表的倒数第1个结点位于位置 L倒数第 n 个结点位于位置 L - n 1慢指针所在的 L - n 1 是什么从后往前数位置 L - n 1 正好是倒数第 n 1 个结点即目标节点的前驱。举个例子链表1 - 2 - 3 - 4 - 5L5n2。fast 先走2步来到3然后 slow 和 fast 同步走fast 从3走到 null 需要3步slow 走3步后从 dummy 来到3的位置也就是节点3。节点3是倒数第3个正好是节点4的前驱slow.next.next就是节点5执行slow.next slow.next.next后节点4被跳过删除完成。3. 栈辅助法空间换时间的直观解3.1 栈的核心思路双指针很巧妙但不是所有人第一时间都能想到。如果觉得双指针抽象可以先理解另一种更符合直觉的方法栈辅助。由于单链表不能倒序访问但我们可以“正着走一遍记下所有节点再从尾部往回数”。具体流程是从头遍历链表把每个节点依次压入栈中。因为栈是后进先出所以链表的尾结点会最先被弹出。我们要删除倒数第 n 个结点就执行 n 次出栈操作弹掉的第 n 个节点正好是目标节点。但问题又来了出栈只能拿到目标节点拿不到它的前驱。因此还要多弹一次这次弹出的节点就是目标节点的前驱。拿到前驱之后执行prev.next prev.next.next即可删除。为了统一处理头结点删除的情况这里同样建议使用虚拟头结点。把 dummy 也压入栈中相当于栈里永远保留了一个起点。这样即使链表只有一个节点并且要删除它多弹一次时栈里还有 dummy不会发生空栈错误。3.2 边界情况处理栈解法的高手之处在于它对边界情况的容错性很强但前提是把虚拟头结点用好。如果忽略 dummy当 n 等于链表长度 L 时目标节点就是 head。这时连续出栈 n 次后栈为空了再想取“前驱”就会抛出空栈异常。加上 dummy 后所有节点总数为 L1倒数第 n1 个节点在栈里的位置始终是存在的于是prev.next prev.next.next依然成立。另一个容易忽略的点是入栈的顺序不能错。必须从 dummy 开始入栈然后遍历原链表把每个节点都压进去一共压入 L1 个节点。如果只压原链表节点那么删除头结点时依然会“无前驱可弹”。建议代码里写成stack [] cur dummy while cur: stack.append(cur) cur cur.next这样 dummy 也在栈底永远不会缺前驱。3.3 栈解法与双指针的复杂度对比从结果上看栈解法同样只遍历了一遍链表时间复杂度是 O(L)。区别在于空间复杂度双指针法只用了两个额外指针空间复杂度 O(1)栈解法额外存储了 L1 个节点引用空间复杂度 O(L)。LeetCode 官方题解里明确指出栈辅助法是“利用数据结构简化问题”的代表非常适合用来向面试官展示你知道如何用空间换取实现的简洁性。方案时间复杂度空间复杂度是否一次遍历直观程度两次遍历O(L)O(1)否最直观双指针O(L)O(1)是需要理解间隔栈辅助O(L)O(L)是符合倒序直觉递归回溯O(L)O(L)递归栈是比较绕如果面试时被要求“不要用额外空间”那答案应该锁定双指针。如果问题没有空间限制直接说栈辅助会让面试官觉得你思路开阔而不是只会背题。4. 递归法和其他思路拓展视野4.1 递归回溯的秒解法递归是一种非常“算法味”的解法它依赖系统调用栈天然的后进先出特性相当于隐式地使用了一个栈。思路是先递归到链表末尾然后逐层返回时维护一个计数器 count。当 count 等于 n 时说明当前节点是要删除的节点。但删除需要前驱所以更好的做法是让递归函数返回“当前节点的下一个节点”一旦发现当前节点是目标节点的前驱就把它的 next 修改为 next.next。Python 的一种实现长这样def removeNthFromEnd(head: Optional[ListNode], n: int) - Optional[ListNode]: def dfs(node): nonlocal count if not node: return None node.next dfs(node.next) count 1 if count n: return node.next return node count 0 dummy ListNode(0, head) dummy.next dfs(dummy.next) return dummy.next这里把目标节点直接“丢掉”了本质上递归返回值是下一层处理后的链表。这种写法并不好读但在面试中你能主动提出来说明对递归边界消化得很透彻。需要注意 Python 里的nonlocal count很多人在这里漏写导致 UnboundLocalError。递归的代价是空间复杂度 O(L)因为递归栈深度等于链表长度。如果链表很长还可能爆栈。这也是为什么递归更适合作为“加分项”而非主要方案。4.2 两次遍历法最简单的基础版两次遍历是大多数人看到题后第一反应能想出的方案也是很多教科书风格的答案。第一步从头到尾遍历链表统计节点总数 L。第二步从头开始走走到第 L - n 个节点时停下这就是目标节点的前驱。然后执行prev.next prev.next.next。为了便于说明定义一个从 1 开始计数的方式倒数第 n 个节点就是正数第 L - n 1 个节点。它的前驱是正数第 L - n 个节点。如果 L - n 等于 0说明没有前驱即要删除头结点这时候单独处理head head.next即可。当然也可以用虚拟头结点统一逻辑。两次遍历的缺陷一目了然链表被完整扫了两遍但没有额外空间时间复杂度仍为 O(L)。它属于“保底方案”适合作为和面试官讨论的起点。比如你可以说“我先用两次遍历保证正确性再优化成一次遍历的双指针。”这种从朴素解法到优化解法的递进叙述是面试中很加分的表达方式。4.3 变体场景删除头结点/尾结点/唯一结点LeetCode 默认 n 是有效值但实际工作中或者面试追问时各种边界场景都可能出现。我们可以把这几种情况单独拎出来想清楚。删除尾结点时倒数第 1 个也就是链表最后一个节点。双指针法里 fast 先走 1 步然后 slow/fast 同步走。fast 到达 null 时slow 指向倒数第 2 个节点也就是尾结点的前驱slow.next slow.next.next会把 next 置为 null正好删除尾结点。如果链表只有一个节点加虚拟头后 slow 从 dummy 出发fast 走 1 步到原节点再同步一步 fast 到 nullslow 停在 dummy删除后 dummy.next 为 null返回 null。一切正常。如果要删除的节点是头结点比如链表长度为 5n5双指针法里 fast 先走5步直接到达末尾 null此时 slow 还在 dummy站在头结点的前驱位置删除后返回 dummy.next头结点被正确移除。这些边界场景只要你用了虚拟头结点几乎都被天然化解了。5. 实战编码完整可运行代码和踩坑记录5.1 按语言给出完整实现双指针法在 LeetCode 上是最推荐的解法这里给出 Python、Java、C 三个版本方便不同语言背景的同学对照。Python 版本class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]: dummy ListNode(0, head) slow fast dummy for _ in range(n): fast fast.next while fast.next: slow slow.next fast fast.next slow.next slow.next.next return dummy.nextJava 版本class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0, head); ListNode slow dummy; ListNode fast dummy; for (int i 0; i n; i) { fast fast.next; } while (fast.next ! null) { slow slow.next; fast fast.next; } slow.next slow.next.next; return dummy.next; } }C 版本class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); ListNode* slow dummy; ListNode* fast dummy; while (n-- 0) { fast fast-next; } while (fast-next ! nullptr) { slow slow-next; fast fast-next; } ListNode* toDelete slow-next; slow-next slow-next-next; delete toDelete; return dummy-next; } };注意 C 版本里我单独保留了toDelete指针然后执行delete。在 C 里删除链表节点后手动释放内存是好习惯不过 LeetCode 刷题环境通常不强制但面试时提出这一点会让面试官觉得你注意到了内存管理。Python 和 Java 的垃圾回收处理了这件事所以不需要手动释放。5.2 我踩过的最典型的 3 个坑坑一是快指针先走几步没想清楚。我最初写的是for _ in range(n - 1)结果 slow 最终落在了目标节点上然后我试图用slow.next slow.next.next逻辑完全错乱。正确理解是快指针先走 n 步最终 slow 才会在前驱位置。这个坑最隐蔽建议写完代码后在[1,2,3,4,5], n2上手动走一遍。坑二是在 while 循环条件上写错过。很多人会写while fast:而不是while fast.next:。这两者在边界上不一样。如果用while fast:循环会在 fast 移动到 null 之后继续尝试访问fast.next直接空指针。正确写法是当 fast.next 为 null 时停止此时 fast 是最后一个节点slow 恰好在前驱位置。仔细想想我们要的是 fast 到达尾部 null 前停下而不是 fast 变成 null 再停。坑三是 C 里释放内存时指针顺序写反。ListNode* toDelete slow-next; slow-next slow-next-next; delete toDelete;这三步必须严格按照这种顺序。如果先执行delete slow-next再执行slow-next slow-next-next右侧的slow-next-next已经是悬空指针程序直接崩溃。这种内存操作的顺序感需要靠刷题练出来。5.3 测试用例怎么设计算法题光提交通过不够你得学会设计测试用例来验证边界条件。我刷这道题时通常会准备这么几组用例链表n期望结果覆盖场景通用场景[1,2,3,4,5]2[1,2,3,5]正常删除中间节点删除头结点[1,2,3]3[2,3]n 等于链表长度删除尾结点[1,2,3]1[1,2]删除最后一个节点唯一节点[1]1[]链表只剩一个节点连续删除[1,2]2[2]n 等于长度且链表较短在本地写题时可以自己定义一个简单的链表节点类和打印辅助函数把所有用例跑一遍确认输出无误再提交。LeetCode 上执行错误时也建议先在草稿纸上模拟一遍不要照抄别人的题解。6. 面试官真正想考什么6.1 不只是题目本身这道题放到面试里考察的是三层能力。第一层是基本功你知道链表节点怎么定义知道改 next 指针就能删除节点。第二层是边界意识头结点删除、单节点链表、n 等于链表长度这些情况能不能主动想到并处理。第三层是优化意识能不能从两次遍历优化到一次遍历能不能说清楚空间复杂度的差异。很多候选人写双指针时会在“fast 先走 n 步还是 n-1 步”这里卡住。面试官并不会因为你卡一次就否定你他们更关心你能不能通过画图、举例子把自己的思路捋清楚。所以模拟面试时我会刻意追问那些细节比如“你能解释为什么 slow 最终指向前驱吗”如果候选人能拿具体链表走一遍说明他真的理解了。6.2 可以延伸的考点这道题还有一个隐藏价值它是一系列快慢指针题的开胃菜。LeetCode 第876题“链表的中间结点”就是同一个框架快指针每次走两步慢指针每次走一步快指针到末尾时慢指针在中点。还有判断链表是否有环同样用快慢指针。如果你能把第19题吃透再去刷这些题会轻松很多。此外栈辅助法还能延伸到“回文链表”判断把链表前半部分入栈后半部分出栈比较。这些都是面试官喜欢把简单题延展成多个连锁问题的出发点。回答的时候如果你能主动补充一句“这道题和876题有共性都是通过两个指针的错位来制造距离”会非常有记忆点。6.3 怎么给面试官留下好印象一个实用的面试话术是先给普通解法再逐步优化。你可以这样开场“这道题我第一时间想到两次遍历因为可以准确知道链表长度。但如果期望一次遍历可以用双指针让快指针先走 n 步然后快慢同时走这样快指针走到底时慢指针正好指向待删除节点的前驱。还可以提一下栈解法虽然空间复杂度高一点但思路更直观。”这段话说完面试官基本就知道你理解得很到位了。再主动提一句虚拟头结点“我在所有链表删除题里都会加一个 dummy 节点这样头结点的删除不用单独判断。”这种习惯性表达比闷头写完代码的效果好得多。当然前提是你真的理解每一步为什么这么做而不是背答案。我个人刷这道题最大的体会是链表题最怕的不是不会写而是自我感觉写对了但边界崩了。后来我养成了一个习惯每次写完链表相关代码第一件事就是走一遍“删除头结点”和“单节点链表”这两个测试用例。把这道题的虚拟头结点和双指针间隔吃透之后你会发现 LeetCode 上一大半链表题都有相似的套路越刷越顺。