1. 题目拆解与能力考察点1.1 题目原文与核心意图链表题是 LeetCode 面试中跑不掉的一关而“删除链表的倒数第 N 个结点”LeetCode 第 19 题又是链表题里最容易被问出花来的题目。很多人看题第一反应是先把链表遍历一遍数出长度再用 长度 - N 定位到要删的结点这种思路虽然能过但面试官往往会在你写完后面露微笑追问一句“能不能只遍历一遍”这时候如果你只会写个两遍扫描基本上就要等下一题了。这道题真正要考察的是你对链表这种“无法直接拿到下标、只能通过指针逐个移动”的数据结构有没有手感以及能不能把双指针、栈这类工具用对场景。无论你是在刷 LeetCode 热门 100 题还是在准备校招机试这道题都值得当成模板题做透。题目本身并不复杂给定一个单链表头结点 head 和一个正整数 n删除从链表末尾算起的第 n 个结点然后返回新的头结点。比如链表是 1 - 2 - 3 - 4 - 5n 2删掉倒数第 2 个结点 4 之后链表变成 1 - 2 - 3 - 5。这里最关键的两个字是“倒数”因为单链表只能从头往后走不能像数组那样直接用下标访问某个位置所以“倒数第几个”天然就是一个需要绕弯子的需求。另外要提醒一句LeetCode 原题会保证 n 一定在有效范围内也就是 1 n 链表长度。但实际面试或者自己写工具函数的时候别人可不一定给你这么舒服的输入。所以我下面讲的所有方案默认都按“n 合法”来写但在边界条件那一节我会专门聊假如 n 超出长度、链表为空时该怎么办这样才能体现防御式编程的意识。1.2 为什么这道题适合作为面试模板题先说结论这道题非常适合拿来检验候选人的基础功底因为它“入口浅、出口深”。入口浅体现在题目描述一句话就能看懂不需要复杂的数学背景出口深体现在解法可以一层一层升级最普通的两次遍历、稍微快一点的一次遍历、用栈的另一种思路、甚至递归倒序删除每种写法的代码量、时间和空间复杂度都不一样。面试官出一道链表题最想看的往往不是你背了多少奇技淫巧而是你写代码的时候有没有考虑边界。具体到这道题至少有四个点值得考察你能不能意识到“删除结点需要拿到它的前驱结点”你能不能处理“删除的正好是头结点”这种特殊情况你能不能想到 dummy node虚拟头结点来统一代码逻辑你能否说清楚 double pointer 为什么能一次遍历解决很多人在纸上画一画能明白但一上手写代码就乱原因就是把上面的问题揉在一起脑子绕不过来了。我在后面会把每一步的“为什么”都拆开讲因为刷题最忌讳的就是背代码你把逻辑吃透换个壳的题你也照样能做。2. 从暴力两遍扫描到一次遍历的思路演进2.1 第一反应先数长度再删第 length - n 个大部分第一次接触这道题的人第一反应都是“两步走”第一步遍历链表数出总长度 length 第二步重新从头走 length - n 步找到要删结点的前驱然后做删除。为什么是 length - n因为如果下标从 0 开始数倒数第 n 个结点正数位置正好是 length - n。举个例子链表有 5 个结点n 2那么倒数第 2 个就是正数下标 3 的结点从 0 开始也就是 4 这个结点。我们要删掉 4就必须先找到它的前驱 3所以再走 length - n - 1 步也能到但更直观的写法是走到 length - n 的位置再通过前驱关系删除具体看你怎么控制指针。C 写法大概是这样的ListNode* removeNthFromEnd(ListNode* head, int n) { int length 0; ListNode* cur head; while (cur) { length; cur cur-next; } ListNode* dummy new ListNode(0, head); ListNode* prev dummy; for (int i 0; i length - n; i) { prev prev-next; } prev-next prev-next-next; ListNode* ans dummy-next; delete dummy; return ans; }时间复杂度是 O(L)这里 L 是链表长度空间复杂度是 O(1)。这种方法毫无问题能 AC代码也很好懂。但它有个明显的“缺陷”链表被完整扫了两遍。虽然时间复杂度里 2L 和 L 都是 O(L)但面试官要的是一个“只扫一遍”的版本。有人可能会杠“多扫一遍又怎样反正都是 O(n)。”确实单从大 O 角度它们没区别但很多实际场景里链表可能非常大甚至存储在磁盘、网络流上每遍历一遍都有成本。更重要的是面试官问“能不能一次遍历”考察的是你有没有想到双指针的模型而不是真的在意那一遍遍历的耗时。2.2 一次遍历到底在优化什么要把两次遍历优化成一次遍历核心是要找到一个办法让“倒数第 n 个”这个位置关系被“拉直”成一个可同步推进的过程。你想想看如果我们在链表头放两个指针一个叫 fast一个叫 slow。先让 fast 往前走 n 步然后两个指针一起往前走。因为 fast 和 slow 中间始终隔着 n 步所以当 fast 走到链表末尾的时候slow 所在的位置刚好就是“从末尾数第 n 个”的位置。这就是双指针法最朴素的想法。但这里有一个非常重要的细节删除需要前驱结点。如果 slow 刚好停在“要删除的结点”上比如停在 4 这个结点你是没法删除 4 的因为你拿不到 3 的 next 指针。所以实际操作时我们要让 slow 停在“要删除结点的前一个结点”上也就是停在 3 的位置。怎么做到呢有两个办法一个是从 head 开始先让 fast 走 n 步然后当 fast 走到最后一个非空结点时停止slow 指向的就是待删结点的前驱。另一个是直接让 fast 先走 n 1 步这样 fast 到末尾时 slow 自然停在待删结点的前驱。第二个办法通常配合虚拟头结点使用逻辑更统一我在下一节重点讲。3. 双指针法一次遍历的标准答案3.1 虚拟头结点为什么值得养成习惯虚拟头结点是链表题里性价比最高的技巧之一。它本质上是创建一个值为任意占位数、next 指向原链表的结点在这个 dummy 结点的基础上做各种指针操作最后返回 dummy-next 作为新链表头。这样做最大的好处是头结点不再特殊。假设你要删除原始链表的头结点没有 dummy 的时候你得写if (prev head) { head head-next; } else { prev-next prev-next-next; }有 dummy 之后你永远只要写prev-next prev-next-next;这一行。因为 dummy 作为哨兵结点垫底即使要删原始 head它的前驱也是 dummy逻辑和其他结点完全一致。我见过不少刷题新手不喜欢用 dummy觉得自己手写一个ListNode* pre head;也行。但实际面试写草稿的时候人一紧张就容易在头结点这里漏判断一旦漏了测试用例里面“n 等于链表长度”这条用例就会挂。你还别不服我见过有人写了三遍都挂在同一个用例上。所以我现在遇到链表删除类问题第一反应永远是“先加一个 dummy。”这已经是肌肉记忆了。3.2 C 完整实现与关键注释用 C 写双指针法我推荐这么写ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); ListNode* fast dummy; ListNode* slow dummy; // 1. fast 先走 n 步 while (n 0) { fast fast-next; --n; } // 2. 两个指针一起走 // 注意这里要用 fast-next ! nullptr 而不是 fast ! nullptr // 因为我们要让 slow 停在待删结点的前驱而不是待删结点本身 while (fast-next ! nullptr) { fast fast-next; slow slow-next; } // 3. 删除 slow 后面的结点 ListNode* toDelete slow-next; slow-next slow-next-next; delete toDelete; // 4. 返回新链表头 ListNode* ans dummy-next; delete dummy; return ans; }第 1 步里fast 从 dummy 出发走 n 步。如果链表长度刚好等于 nfast 走完后会变成 nullptr。那么第 2 步while (fast-next ! nullptr)就会直接访问空指针这是有些人写着写着就崩掉的原因。所以如果你想让代码更防御式可以改成while (fast ! nullptr fast-next ! nullptr) { fast fast-next; slow slow-next; }这样当 fast 为 nullptr 时循环不会执行slow 停在 dummy。然后slow-next slow-next-next删掉原始头结点结果一样正确。不过 LeetCode 原题保证 n 合法很多人就懒得加这个判断。但如果你的代码是要给人 review 或者要放进项目里的我还是建议多写一个条件免得某天被奇怪的数据输入坑到。3.3 Python 与 Go 的对应写法Python 版的思路完全一样只是语法更简洁。我提供一份常见写法class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]: dummy ListNode(0, head) fast dummy slow dummy for _ in range(n): fast fast.next while fast and fast.next: fast fast.next slow slow.next slow.next slow.next.next return dummy.next注意这里while fast and fast.next相当于把 n 链表长度的情况也处理了因为 fast 会变成 None循环直接跳过。如果你写成while fast.next当 n length 时 fast 是 None会直接抛 AttributeError。Python 这种动态语言不会像 C 一样段错误但报错信息同样会让你停下来调半天。Go 版本我也放一下func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy : ListNode{Next: head} fast : dummy slow : dummy for ; n 0; n-- { fast fast.Next } for fast.Next ! nil { fast fast.Next slow slow.Next } slow.Next slow.Next.Next return dummy.Next }Go 的写法跟 C 很接近但要注意 Go 里没有 C 那种手动 delete 的负担垃圾回收会帮你处理。不过这也意味着你需要想得更清楚删除链表结点只是断开了引用关系原来那个结点对象如果还被别的变量引用它就不会立刻被回收。从这三份代码你能看出双指针法在不同语言里的骨架一模一样。所以我一直建议刷题的人别只盯着一种语言至少在脑内把“指针移动”的逻辑用自然语言描述清楚换语言只是换语法而已。3.4 为什么 fast 先走 n 步而不是 n - 1 步这个问题几乎每次讲这题都会被问到。你如果自己试着写一遍很可能一开始会写成先走 n - 1 步结果发现最后 slow 停在待删结点上而不是它的前驱然后你就得再想怎么往前回退。但单链表根本没法回退所以只能改循环条件。我们来推一下假设链表长度是 L目标是从末尾数第 n 个结点。如果让 fast 先走 n 步此时 fast 和 slow 之间隔着 n 步。然后两者同步走当 fast 走到 null 时slow 的位置就是“从末尾数第 n 1 个结点”也就是我们要删结点的前驱。举个例子链表 1 - 2 - 3 - 4 - 5n 2。fast 从 dummy 走两步到 2slow 在 dummy。接着一起走fast 到 5 时 slow 到 3fast 再走一步到 null 时 slow 到 4 等一下这里要分清楚循环停止条件。如果循环是while (fast-next ! nullptr)那 fast 到 5 的时候就停了此时 slow 到 3。3 正是 4 的前驱所以效果对。如果循环是while (fast ! nullptr)那 fast 到 null 时才停slow 会到 4 本身那就错了。所以大家看到的常见写法都是while (fast-next ! nullptr)。那如果 fast 先走 n - 1 步呢fast 会先到结点 1不对比如 n 2fast 先走 1 步到结点 1然后快慢指针同步走直到 fast 到最后一个结点 5slow 到结点 4。这样 slow 停在待删结点上没法直接删。除非你后面拿到 slow-next 往前删但单链表做不到。所以正确姿势就两条路要么让 fast 先走 n 步slow 停在待删结点的前驱要么让 fast 先走 n 1 步循环条件改成while (fast ! nullptr)slow 也停在待删结点的前驱。实际工程里大家更习惯前者。4. 栈辅助法换一种数据结构看倒数问题4.1 栈在“倒数”场景里的天然优势很多初学者不知道双指针并不是这道题唯一的“高级”解法。用栈也能轻松解决而且思路特别直观。“倒数第 n 个结点”这个说法翻译成栈的语言就是“把所有结点按从头到尾的顺序压进去然后从栈顶往外弹弹到第 n 个就是我们要删的结点。”因为栈是后进先出压栈顺序为正出栈顺序就变成反的倒数问题一下子被倒过来了。这种解法的好处是你完全不用纠结什么前驱、后驱。你把所有结点都压进栈之后弹出 n 个结点此时栈顶元素就是待删结点的前驱结点。然后直接做一次删除操作就行。当然这个方案的代价是空间复杂度 O(L)因为你需要用一个额外的栈来装所有结点。对于 LeetCode 这种数据量不算大的题空间完全够用但如果你设计系统代码就要权衡一下“省时间”和“省空间”哪个更重要。4.2 基于栈的代码实现与空间复杂度分析用 C 的 stack 容器可以写得很短ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); ListNode* cur dummy; stackListNode* st; while (cur ! nullptr) { st.push(cur); cur cur-next; } // 弹出 n 个结点后栈顶就是要删结点的前驱 while (n-- 0) { st.pop(); } ListNode* prev st.top(); prev-next prev-next-next; ListNode* ans dummy-next; delete dummy; return ans; }仔细看这里连 dummy 也压进去了。为什么要压 dummy因为如果链表只有一个结点n 1弹出那个结点后栈里就剩下 dummy这样st.top()仍然有效prev-next就是 null删除后链表变成空。如果不压 dummy你弹完 n 个结点后栈是空的st.top()直接未定义行为。如果你不想用标准库的 stack用 vector 或者 array 模拟也是一样的。只要记住“先入栈、再出栈、找到前驱、删除”这四个步骤即可。空间复杂度是 O(L)因为栈最多存 L 1 个结点指针。时间复杂度是 O(L)每个结点入栈一次、出栈一次也都是常数次操作。和双指针法相比它的主要优点是代码更不容易写错尤其适合在讨论算法思路时作为“第二方案”展示给面试官。如果你先写了双指针法面试官又问“还有没有别的思路”能立刻说出栈解法会显得你脑子里不只是背了一板斧而是真的理解“用额外数据结构把遍历顺序倒过来”的思想。5. 边界条件、测试用例与避坑清单5.1 瞬间就能测出 bug 的 6 组用例刷 LeetCode 时测试用例是系统帮你跑好的。可要是你平时自己刷题、写工具函数或者要给别人 review 代码就得学会自己设计边界用例。我最常用来检查这道题实现是否正确的一组用例如下用例编号链表输入n期望输出实际测试重点1[1,2,3,4,5]2[1,2,3,5]标准场景2[1,2,3]1[1,2]删最后一个结点3[1,2,3,4]4[2,3,4]删头结点4[1]1[]只有一个结点删完变空5[1,2]2[2]删头结点且剩一个结点6[1,2,3]3[2,3]n 长度等价删头结点很多人在第 3 组和第 4 组栽跟头。第 3 组考验你有没有做好“删除头结点”的处理第 4 组考验你栈解法里有没有把 dummy 压进去、双指针解法里有没有正确处理 fast 变成 nullptr 的情况。比如用双指针且只写while(fast-next ! nullptr)那种版本遇到第 3 组用例就崩。用栈解法但忘记压 dummy遇到第 4 组用例也崩。所以每次写完这段代码我至少会把这 6 组用例在脑子里过一遍确认没问题再提交。5.2 自己踩过的几个坑这题我至少给四五个人 review 过自己也踩过几个真实存在的坑。这里挑三个最典型的说说。第一个坑删除前没有保存待删结点直接改了 next 但忘了释放内存。C 写法里如果slow-next指向一个 new 出来的结点你直接slow-next slow-next-next会导致那个结点内存泄漏。虽然 LeetCode 不校验内存泄漏但公司代码 review 一定会有人指出来。正确做法是把待删结点先存下来删除后 delete 掉。第二个坑返回的 head 被删了但你仍然返回了原来的 head 指针。很多人写双指针时不加 dummy而是直接返回 head。如果 n 正好等于链表长度删除的是原始 head但你返回的还是那个已经被删掉的 head整个链表就丢了。解决办法就是从头到尾用 dummy最后返回 dummy-next彻底避免这个逻辑纠纷。第三个坑递归解法。偶尔有人会想用递归先递归到链表尾部再回溯的时候计数数到第 n 个就删。这种思路不是不行但当链表很长的时候递归深度会非常大容易爆栈。比如一个十万个结点的链表除非你把递归深度限制改掉否则很危险。所以我在项目中几乎不用递归处理这种问题面试时如果非要多给一种解法我更愿意说栈辅助法而不是递归。还有一个偏经验层面的技巧题目里虽然 n 被保证合法但你自己写的时候还是要想想如果 n 等于 0 呢如果 n 是负数呢从工程角度n 0 可以直接原样返回或者在入口处抛异常。LeetCode 不会测这些但你设计一个公共工具函数时这种防御式检查是判断你“有没有工程素养”的分水岭。6. 实战中的算法思维拓展6.1 快慢指针的通用套路不只是这一题双指针法在链表题里是一套通用方法论绝对不止“删除倒数第 N 个结点”这一个场景。我顺手列举几个常见的亲戚题查找单链表中间结点快指针每次走两步慢指针每次走一步快指针到尾时慢指针就在中间。这就是 876. Middle of the Linked List 的核心思路。判断链表是否有环快慢指针如果存在环最终必然相遇。这就是 141. Linked List Cycle 的经典解法。寻找环的入口快慢指针相遇后再用一个新指针从 head 出发和慢指针同步走两者相遇点就是环入口。这是 142 题的思路。链表相交问题A 链表的指针走完后跳到 B 链表的头继续走B 同理两个指针相遇的位置就是相交点。这是 160 题的思路。你会发现这些题目并没有统一模板但它们都共用同一种思维模型“用两个不同速度或不同起点的指针在单链表上构造出一个相对距离把这个相对距离变成解题线索。”如果你把第 19 题真的吃透了再去做上面这些题理解速度会快很多。我习惯把这几个题放在一起集中刷因为它们互相印证。第一遍可能只是“哦原来这么做”第二遍开始尝试不看题解手写第三遍就尝试说清楚每一步指针移动的意图。能说到第三步基本就内化成自己的东西了。6.2 如果题目换个姿势你还会做吗面试官大概率不会只问你原题他可能会做以下的变化改成“删除倒数第 N 个结点并返回新链表头”的变体。这其实和原题一样只是把你返回的值拿去干什么做了点变化。改成“找到倒数第 N 个结点并且输出它的值”。那就更简单了只需要双指针不需要删除也就不用考虑前驱。改成“移除链表中的重复元素”。这题走了另一个方向不再看倒数而是看相邻结点值是否相同。改成“旋转链表”让你把链表右移 k 个位置。这个题其实也用到了“先找到倒数第 k 个结点”的思路因为你得先找到新的头结点和新的尾结点再把链表重新串起来。我没有夸张如果你会做第 19 题的双指针法看第 61 题 Rotate List 会感觉特别亲切。所以刷题真不是刷完一遍就结束而是应该问自己如果题目条件改一改我会不会做如果能像上面这样把题串起来你就开始从“刷题者”变成“用题者”了。我个人在实际操作中的体会是这道题最适合用来做“一题多解”练习的起点。你先用两遍扫描写一遍再用双指针写一遍再用栈写一遍然后比较三种写法的时间空间消耗。这个过程做完你收获的不只是这一题的答案而是下一次碰到“倒数第 K 个”问题时你脑子里能立刻蹦出三四种方案然后在白板上挑最合适的一个写。这种“有余力、能选择”的状态才是面试官真正想看到的。最后再分享一个小技巧链表题永远记得先画图再写代码。哪怕只是在草稿纸上画三个方框加两根箭头也比直接硬想指针怎么跳要靠谱一百倍。这道题我每次给新手讲都要求对方先画一遍 fast 先走、slow 跟上的过程画完以后所有 bug 都会自动消失。