删除链表倒数第N个结点：双指针一次遍历的经典解法

1. 题目拆解与能力考察点

1.1 题目原文与核心意图

链表题是 LeetCode 面试中跑不掉的一关，而“删除链表的倒数第 N 个结点”（LeetCode 第 19 题）又是链表题里最容易被问出花来的题目。很多人看题第一反应是先把链表遍历一遍数出长度，再用 长度 - N 定位到要删的结点，这种思路虽然能过，但面试官往往会在你写完后面露微笑，追问一句“能不能只遍历一遍？”这时候如果你只会写个两遍扫描，基本上就要等下一题了。这道题真正要考察的，是你对链表这种“无法直接拿到下标、只能通过指针逐个移动”的数据结构有没有手感，以及能不能把双指针、栈这类工具用对场景。无论你是在刷 LeetCode 热门 100 题，还是在准备校招机试，这道题都值得当成模板题做透。

题目本身并不复杂：给定一个单链表头结点 head 和一个正整数 n，删除从链表末尾算起的第 n 个结点，然后返回新的头结点。比如链表是 1 -> 2 -> 3 -> 4 -> 5，n = 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 步。如果链表长度刚好等于 n，fast 走完后会变成 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 -> 5，n = 2。fast 从 dummy 走两步到 2，slow 在 dummy。接着一起走：fast 到 5 时 slow 到 3，fast 再走一步到 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 = 2，fast 先走 1 步到结点 1，然后快慢指针同步走，直到 fast 到最后一个结点 5，slow 到结点 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; stack<ListNode*> 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 代码，就得学会自己设计边界用例。我最常用来检查这道题实现是否正确的一组用例如下：

很多人在第 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 如果题目换个姿势，你还会做吗

面试官大概率不会只问你原题，他可能会做以下的变化：

1. 改成“删除倒数第 N 个结点，并返回新链表头”的变体。这其实和原题一样，只是把你返回的值拿去干什么做了点变化。
2. 改成“找到倒数第 N 个结点并且输出它的值”。那就更简单了，只需要双指针，不需要删除，也就不用考虑前驱。
3. 改成“移除链表中的重复元素”。这题走了另一个方向，不再看倒数，而是看相邻结点值是否相同。
4. 改成“旋转链表”，让你把链表右移 k 个位置。这个题其实也用到了“先找到倒数第 k 个结点”的思路，因为你得先找到新的头结点和新的尾结点，再把链表重新串起来。我没有夸张，如果你会做第 19 题的双指针法，看第 61 题 Rotate List 会感觉特别亲切。

所以刷题真不是刷完一遍就结束，而是应该问自己：如果题目条件改一改，我会不会做？如果能像上面这样把题串起来，你就开始从“刷题者”变成“用题者”了。

我个人在实际操作中的体会是，这道题最适合用来做“一题多解”练习的起点。你先用两遍扫描写一遍，再用双指针写一遍，再用栈写一遍，然后比较三种写法的时间空间消耗。这个过程做完，你收获的不只是这一题的答案，而是下一次碰到“倒数第 K 个”问题时，你脑子里能立刻蹦出三四种方案，然后在白板上挑最合适的一个写。这种“有余力、能选择”的状态，才是面试官真正想看到的。

最后再分享一个小技巧：链表题永远记得先画图，再写代码。哪怕只是在草稿纸上画三个方框加两根箭头，也比直接硬想指针怎么跳要靠谱一百倍。这道题我每次给新手讲，都要求对方先画一遍 fast 先走、slow 跟上的过程，画完以后，所有 bug 都会自动消失。