LeetCode 19：双指针删除链表倒数第N个结点全解析

我在技术面试里最爱用的一道链表题，就是LeetCode经典算法面试题#19：删除链表的倒数第N个结点。这道题看起来人畜无害，却能一次性考察到链表遍历、双指针、边界处理和编码基本功四个维度；如果候选人主动提到栈辅助法，还能顺势把空间复杂度权衡拉进讨论。今天我就把这题的多种实现方案、每一步的为什么、以及面试里真正容易翻车的细节，完整拆开来讲。

文章适合两类人看：一是准备算法面试、刷LeetCode热门100题的读者，二是已经在用链表做业务开发、想补一补底层基本功的同学。前者可以照着代码逐行理解双指针的精髓，后者能从中提炼出"指针操作前先想清楚前驱依赖"这一类的工程习惯。

1. 题目到底在考什么：一句"倒数第N个"背后的链表特性

1.1 原题描述与输入输出约束

原题描述很简短：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例：head = [1,2,3,4,5]，n = 2。这个链表的倒数第2个结点是4，删掉之后变成 [1,2,3,5]。

题目给出的约束值得逐条看：

• 链表中结点的数目为 sz，范围是 1 到 30。
• n 的范围是 1 到 sz，也就是说题目保证 n 一定在有效范围内，链表至少有一个结点。
• 进阶要求：尝试使用一趟扫描实现。

前两条约束意味着你不需要处理"n 大于链表长度"或"链表为空"的非法输入。但我后面会花一整节专门讨论这些边界，因为面试官不会只满足于"题目通过"，他大概率会追问"如果 n 不合法你会怎么防御"。

1.2 为什么"倒数第N个"是这道题最难的点

数组里找倒数第N个元素很简单：直接arr[length - N]下标定位，O(1) 搞定。但单向链表没有随机访问，每条节点只知道自己的 next 指向谁，既不能倒退，也不能跳着走。想找倒数第N个，你必须先想清楚一个残酷的前提：走到链表尾部之前，根本不知道"倒数"到底在哪里。

这是个天然的信息不对称问题。生活里有个很贴切的类比：单向链表就像一条只能单向通行的窄巷，你站在巷口，目标是倒数第N间屋子。你不知道巷子总共有多长，只能一路往前走，等走到头折返回来数。问题是你不能折返，因为链表的指针方向是固定的。

那怎么办？人的第一反应是：先走到头数清楚总长度，再从头走到目标位置。这就是两次遍历方案。而更聪明的做法是：找另外一个参照物跟你同时走，利用距离差，让你走到头的时候，参照物恰好停在目标节点的前一个位置。这就是双指针。理解到这个层面，"倒数"的难点就转化成了一个距离问题，而不再是一个遍历次数问题。

2. 最朴素的两次遍历：先算长度再定点删除

2.1 为什么推荐先写这个版本

别觉得两次遍历"不够高级"就跳过。我见过不少候选人上来就背双指针的模板，结果被面试官问一句"那你说说 first 指针为什么要先走 n 步而不是 n+1 步"就直接卡壳。而两次遍历的思路天然符合人的直觉，是理解一切后续优化方案的地基。

它的完整流程分三步：

1. 找长度：从头节点开始遍历，数出链表总长度 L。
2. 算目标：要删除倒数第 N 个节点，等价于删除正数第 L - N + 1 个节点。
3. 走到前驱：遍历到正数第 L - N 个节点（也就是目标节点的前驱），执行 pre.next = pre.next.next。

这里第一步算是很直白，为什么第三步要强调"走到前驱"？因为单向链表的删除操作本质上不是"删除自己"，而是"让前一个节点绕过自己"。你没有能力让一个节点凭空消失，你能做的只是断开前驱指向它的引用，让 GC 或者手动内存管理去回收它。这个"前驱依赖"的理解，是这道题和后续所有链表删除类题目的共同底层逻辑。

2.2 C++ 实现与逐行注释

ListNode* removeNthFromEnd(ListNode* head, int n) { // 第一次遍历：计算链表长度 int length = 0; ListNode* cur = head; while (cur != nullptr) { length++; cur = cur->next; } // 目标：删除正数第 length - n + 1 个节点 // 需要走到它的前驱，也就是正数第 length - n 个节点 int targetPrevIndex = length - n; ListNode* pre = head; // 特判：如果要删除的是头节点，pre 应该是一个虚拟前驱 if (targetPrevIndex == 0) { ListNode* newHead = head->next; return newHead; } // 走到前驱节点 while (--targetPrevIndex > 0) { pre = pre->next; } // 也可以写成 for (int i = 0; i < targetPrevIndex - 1; i++) pre = pre->next; // 删除目标节点 ListNode* toDelete = pre->next; pre->next = pre->next->next; delete toDelete; // 视语言和实际场景决定是否需要释放 return head; }

这段代码里最需要留意的是那个if (targetPrevIndex == 0)的特判。当要删除的是头节点时，它没有前驱，所以只能直接修改 head。这是两次遍历方案里最容易被忽略、也最容易写错的地方。

2.3 朴素方案的两个坑：长度计算与头结点特判

这个方案的坑主要集中在两处。

第一个坑是长度计算。很多人习惯用"从 head 开始，cur != nullptr 就 +1"的方式数节点数。这没问题，但要注意如果你初始化 cur = head->next，那长度就会少 1，后面算 targetPrevIndex 也跟着错，而且这种错很难通过看代码发现，只能靠测试用例抓出来。

第二个坑就是上面的头节点特判。如果删除的恰好是头节点，你必须直接返回 head->next，否则 return head 会把已经删除的头节点再返回回去。LeetCode 的判题逻辑不会告诉你"你的返回值和期望值在头节点删除场景下差了一个节点"，只会显示 Wrong Answer，非常恶心。所以我后来一直强调一个习惯：凡是涉及链表删除的题，先问自己一句"如果删的是头节点，我的代码走哪条分支"。这个问题能拦住面试里至少三成的候选人。

两次遍历的时间复杂度是 O(L)，空间复杂度 O(1)。L 是链表长度。这个解法的优点是绝对不容易写错，缺点是跑了整整两趟指针，而题目进阶要求明确说"一趟扫描实现"，这就轮到双指针出场了。

3. 双指针法：一趟扫描的精髓与代码细节

3.1 快慢指针的物理含义：制造一个长度为N的滑动窗口

双指针法的核心思想，用一句话概括：让两个指针之间始终保持 N 个节点的距离，然后同步往前走，当第一个指针到达链表末尾时，第二个指针恰好停在倒数第 N 个节点的前驱位置。

我具体解释一下这个"恰好"是怎么来的。假设有两个指针，初始都指向链表头节点。first 先走 N 步，这时 first 指向的是正数第 N+1 个节点，second 还停留在第 1 个节点，两者之间的距离恰好是 N 个节点。接着 first 和 second 以同样的速度同步移动，这个距离会一直保持为 N。当 first 走到链表的末尾空指针（nullptr）时，second 距离末尾也是 N 个节点，也就是 second 正在倒数第 N 个节点上。

这里有一个很关键的工程细节：你最终要做的是删除操作，而删除需要操作目标节点的前驱。所以如果你让 second 停在倒数第 N 个节点本身，你还得额外记一个 pre 变量维护前驱，或者再走一遍。这很麻烦。一个更干净的做法是让 second 一开始就指在一个虚拟头节点上，让 first 多走一步，这样当 first 走到末尾时，second 恰好停在目标节点的前驱上。两种写法的细微差别，我下面详细对比。

3.2 dummy节点（哑节点）的价值：统一头结点删除的代码路径

刚才两次遍历方案里，头节点删除是一个必须特判的边界条件：它没有前驱。而双指针方案普遍使用一个 dummy（哑节点）来消除这个特判。

dummy 是一个值随意、next 指向 head 的额外节点。有了它，头节点也有了"前驱"——即 dummy 本身。这样无论删除的是头节点还是普通节点，删除逻辑统一为"让某个节点的前驱跳过它"，代码里不再需要任何 if (删除的是头节点) 分支。

具体实现时，second 指针从 dummy 开始。即使链表只有 1 个节点，要删除的就是头节点，second 也依然有前驱可操作：second 指向 dummy，执行 second->next = second->next->next 就能把头节点摘掉。这个技巧几乎所有 LeetCode 链表题都能用，建议直接养成习惯。

3.3 完整实现：C++ 和 Python 各给一版

先看 C++ 版，我用的是"first 先走 N 步，然后 first 和 second 同时走到 first 为 nullptr"的写法：

ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(0, head); ListNode* first = head; ListNode* second = dummy; // first 先走 n 步 for (int i = 0; i < n; ++i) { first = first->next; } // 同步移动，直到 first 到达末尾 while (first != nullptr) { first = first->next; second = second->next; } // 此时 second 指向倒数第 n 个节点的前驱 ListNode* toDelete = second->next; second->next = second->next->next; delete toDelete; return dummy->next; }

这个版本里 first 从 head 起步，second 从 dummy 起步。first 走了 N 步之后，first 与 second 之间的距离是 N 个节点；当 first 走到 nullptr，second 正好在倒数第 N 个节点的前驱。我建议你在纸上推演一个具体例子，长度 5、n 等于 2 那种，走一遍就会彻底明白。

再看 Python 版，逻辑完全一致，只是 Python 不需要手动释放节点：

class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy = ListNode(0, head) first = head second = dummy for _ in range(n): first = first.next while first: first = first.next second = second.next second.next = second.next.next return dummy.next

3.4 为什么first先走n步而不是n+1步：两种写法的对比

我第一次学双指针时最困惑的问题就是：为什么有人先说 first 先走 N 步，有人先说先走 N+1 步？这两个方案都对，区别只在于 second 的起始位置。

写法一（上面的实现）：first 从 head 出发走 N 步，second 从 dummy 出发。first 走完后，二者之间隔着 N 个节点，然后同步前进。当 first == nullptr 时，second 指向倒数第 N 个节点的前驱。这里的关键是 second 起点比 first 起点靠前一个节点（dummy 在 head 之前），所以虽然距离是 N，但 first 走到底时 second 落在前驱位置上。

写法二：first 和 second 都从 dummy 出发，first 先走 N+1 步。因为 first 比 second 多走了 N+1 个节点，同步移动后 first 到 nullptr 时，second 同样是目标前驱。两种写法本质相同，只是"把哑节点算进步数"和"把哑节点设为起点"的区别。

那题目标准答案为什么普遍采用写法一？因为它步骤更少，遍历更简洁：first 从 head 走 N 步，循环里少加一个 1，不容易犯边界错误。写法二在讲解时更对称，适合课堂推导。面试时我建议用写法一，背熟了不容易乱。

这里有一个细节新手最容易踩：走完 N 步之后，while 循环的判断条件到底是while (first != nullptr)还是while (first->next != nullptr)？这个差异取决于你要不要多走一步。我们的目标是让 first 走到 nullptr（越出链表末尾），所以用while (first != nullptr)。如果你写成了while (first->next != nullptr)，那 first 会停在最后一个节点上，second 对应的位置就会偏前一个节点，删除结果错位。

3.5 双指针方案的复杂度是真正的一趟扫描

时间上，first 指针从头到尾走过一遍，加上开头 N 步，总共 O(L)；空间上，只用了两个指针，O(1)。

很多人会问：两次遍历 O(2L) 和双指针 O(L + N) 在大 O 复杂度表示里都是 O(L)，为什么还要优化？因为工程里常量系数有意义。当链表节点数量级很大、删除频繁时，少遍历一趟省下的时间实实在在。更重要的理由是题目有"一趟扫描"的进阶要求。除此之外，面试官能从这里打开话题：既然快慢指针可以保持固定距离找倒数第 N 个，那保持一倍速差能不能找中间节点？保持两倍速差能不能判断环？这个问题我放到后面的延伸章节展开。

4. 栈辅助法与其他方案：换一种数据结构看问题

4.1 栈方案的核心思路：后进先出天然匹配"倒数"

如果双指针没想明白，还有一个理解成本极低的方案——栈辅助法。它的逻辑非常直白：把链表所有节点依次压入栈中，然后从栈顶弹出 N 个节点。因为栈是后进先出，最后入栈的是链表尾节点，弹出的第 N 个节点，恰恰就是倒数第 N 个节点。

但删除需要前驱，所以弹出 N 个之后，栈顶剩下的那个节点，就是我们要找的前驱。代码如下：

ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(0, head); stack<ListNode*> stk; ListNode* cur = dummy; while (cur != nullptr) { stk.push(cur); cur = cur->next; } // 弹出 n 个节点，栈顶剩余的就是目标节点的前驱 for (int i = 0; i < n; ++i) { stk.pop(); } ListNode* prev = stk.top(); ListNode* toDelete = prev->next; prev->next = prev->next->next; delete toDelete; return dummy->next; }

注意一个细节：入栈时我从 dummy 开始，而不是从 head 开始。这样做的理由是，当链表长度为 n、需要删除头节点时，弹出 n 个节点之后栈里至少还留着 dummy。如果从 head 开始入栈，链表长度为 n 时会遇到"弹出全部节点后栈为空，无法获取前驱"的尴尬，又得额外特判。从 dummy 起步入栈，直接消灭了这种边界问题，和双指针方案里的 dummy 起到了同样的作用。

4.2 递归方案：为什么面试中只值得提一嘴

还有人可能想到递归：递归天然能先走到链表末尾，回溯时每往回退一层计数加一，计数到 n 时做删除操作。思路是可行的，而且代码非常简洁。

ListNode* removeNthFromEnd(ListNode* head, int n) { if (head == nullptr) return nullptr; head->next = removeNthFromEnd(head->next, n); return head; }

但我并不推荐在正常的算法面试里用递归写这道题。核心原因有三个：

1. 空间复杂度 O(L)，当链表很长时，递归深度等于链表长度，存在栈溢出风险。
2. 删除语义在黑盒里很难说清——递归回溯时你拿到的"当前节点"是第几个，需要额外的计数器或成员变量配合，代码维护起来反而更绕。
3. 面试官问"一趟扫描"时，递归回溯的次数也是一趟扫描的逻辑，但它的额外空间开销让这个方案不是最优解。

因此递归方案适合作为思维拓展提一句，不适合作为主答方案。我把它写在这里，主要是帮大家建立"不同数据结构的特性不同"的直觉：栈的先进后出、递归的回溯、双指针的距离差，都能解决"倒数"这个问题，但各有代价。

4.3 三种主流方案复杂度对比

栈辅助法在空间上确实不如双指针优雅，但它的正确率很高，在高强度面试压力下，如果你一时想不起双指针的停止条件，栈方案是最稳妥的保底手段。我自己刷题时就有一条经验：面试短时间内追求的不是最优解，而是绝对正确的解。先用稳妥方案拿分，再提一句"我知道有双指针的 O(1) 空间解法"，通常比死磕最优解却写出一堆边界 bug 要好得多。

5. 边界情况盘点与实战中的防御性写法

5.1 删除头结点、单节点链表、n=1：三条必须走通的路径

LeetCode 的测试用例覆盖很全，但你自己动手写代码时，至少要主动推演三条路径：

第一条，删除头节点。链表长度为 5，n 等于 5。双指针里 first 从头节点走 5 步之后直接变成 nullptr，second 还停在 dummy 上。此时 second->next 就是原来的 head，执行 second->next = second->next->next 会得到空链表。这条路径如果没了 dummy，代码会直接崩。

第二条，链表只有一个节点，n 等于 1。这是最极端的案例：删除唯一一个节点，返回空链表。双指针里 first 从 head 走 1 步即 nullptr，second 在 dummy 上，删除后 dummy->next 为 nullptr，返回结果正确。

第三条，n 等于 1，删除的是最后一个节点。first 先走 1 步，然后同步移动。当 first 走到 nullptr 时，second 停在倒数第 1 个节点的前驱上，也就是正数第 L-1 个节点。执行删除后，原链表最末尾节点被摘除。这条路径需要特别注意 first 的停止位置：如果 while 条件写成了first->next != nullptr，first 就会停留在最后一个节点而不是越出链表，second 会停在倒数第 2 个节点的前驱，删除的节点就错了。

每次写完代码，把这三条路径在心里或者草稿纸上走一遍，比盲目跑十个测试用例都管用。

5.2 工程上n越界时的处理方式

题目约束 n 一定有效，但真实工程里你面对的数据永远可能不合法。如果你把双指针原样搬到生产代码里，n 大于链表长度时会怎么样？first 走 N 步的过程中已经走成了 nullptr，然后 while 循环里继续访问 first->next，直接对空指针解引用，崩了。

工程上我一般这样处理：把"先走 n 步"改成边走边检查，一旦 first 已经为空且还需要继续走，说明 n 超过了链表长度，直接返回原链表头节点或者抛出参数异常。示例代码如下：

ListNode* removeNthFromEndSafe(ListNode* head, int n) { if (head == nullptr || n <= 0) return head; ListNode* dummy = new ListNode(0, head); ListNode* first = head; ListNode* second = dummy; // 防止 n 越界：步数走完之前 first 不能先为空 for (int i = 0; i < n; ++i) { if (first == nullptr) { // n 大于链表长度，参数非法 return head; } first = first->next; } // 后续逻辑不变 ... }

防御性编程不见得能让你在 LeetCode 上多拿分，但它决定了一个人能不能把算法题的思想安全地迁移到业务代码里。我自己在团队 code review 时，看到链表操作没有空指针保护，一定会多问一句边界情况。

5.3 面试官的典型追问：从"删除"到"查找"

这道题在面试里最常见的追问是：如果题目改成"返回倒数第 N 个节点，而不是删除它"，你的代码要怎么改？

这个追问背后的考点是：你有没有理解双指针的"最终停止位置"取决于目标。删除需要前驱，所以 second 要落在目标前驱；查找只需要目标本身，所以 second 可以直接从 head 出发，与 first 同步移动，当 first 走到 nullptr 时 second 正好在目标节点上。代码甚至更简单：

ListNode* findNthFromEnd(ListNode* head, int n) { if (head == nullptr || n <= 0) return nullptr; ListNode* first = head; ListNode* second = head; for (int i = 0; i < n; ++i) { if (first == nullptr) return nullptr; first = first->next; } while (first != nullptr) { first = first->next; second = second->next; } return second; }

你看，只是把 second 的起始位置从 dummy 挪到 head，并且删掉了删除语句，整个函数就变成查找了。这提醒我们，学算法题不要死记模板，要理解每一步存在的理由：dummy 是为删除前驱服务的，second 的起始位置决定了它是当前驱还是当前节点。

6. 从这一题延伸出去的链表双指针家族

6.1 找链表的中间结点：快慢指针的经典变体

一旦你理解了"距离差"这个工具，双指针的适用范围就打开了。最经典的延伸题是 LeetCode 876：给定一个链表，找到它的中间节点。

思路是快指针每次走两步，慢指针每次走一步。当快指针走到链表末尾时，慢指针恰好走到中间位置。与删除倒数第 N 个节点不同的是，这次双指针的距离不是固定的 N，而是动态拉开的步数差，但本质上仍然是"利用两个指针不同的速度，制造位置差"。

这个题的快慢指针写法有个细节：快指针能不能一次走三步？可以，但慢指针的位置就不是正中间了，需要重新推导公式。所以面试时一般只用步长 2 的组合。

6.2 环形链表检测：双指针从"距离差"升级为"追及问题"

如果链表有环，快慢指针的应用就更有趣了。LeetCode 141 判断链表是否有环，做法是快指针每次走两步，慢指针每次走一步。如果链表无环，快指针先到末尾；如果有环，快慢指针必然在环内相遇。这就从"距离差"升级成了"追及问题"。

环入口的查找（LeetCode 142）用到了更深的数学推导：相遇之后，一个指针从头节点出发，另一个从相遇点出发，两指针以相同速度移动，再次相遇的位置就是环的入口。这个推导我们这里不展开，但它是一个很好的进阶练习，能帮你把双指针的直觉从"固定差"扩展到"追及"。

我认为刷题不要贪多，把这题和 LeetCode 876、141 放在一起学，会非常高效，因为它们的核心是一个共同的思维模型：用指针的步速关系制造位置信息。

6.3 双指针思维在数组场景的迁移

链表里的双指针只是双指针范式的一个分支，同一种思路在数组中也非常常见，比如有序数组的两数之和（LeetCode 167）、盛最多水的容器（LeetCode 11）。它们本质上都是利用指针的移动方向，把暴力枚举的 O(N^2) 降成 O(N)。

学完这一题，你可以在笔记本上记一条主线：凡是"找某个相对位置"的问题，先想想能不能用快慢双指针或者左右双指针。链表题先想快慢，有序数组先想左右。这个思维习惯比多做二十道题都管用。

7. 我用这道题当面试题时观察到的事

最后聊点私人经验。我面试候选人时出这道题，通常能观察到以下规律：大约一半的人能比较顺利地写出两次遍历；能写出双指针的约占三成；能主动提"栈辅助法也可以，但空间复杂度更高"的候选人，往往对复杂度的意识更强。最容易翻车的点，果然还是头节点删除和 while 循环停止条件两个位置，和我在上面专门标出来的完全一致。

所以我给正在准备算法面试的读者一个非常具体的建议：别再满足于把题解代码抄一遍跑过就完事。试着做三件事：

• 第一，把代码里的 dummy 去掉，重新实现一遍，体会 dummy 到底帮你省了多少边界判断。
• 第二，把删除改成查找，再改成返回倒数第 N 个节点的前驱，自己改一遍代码，感受一下 second 起始位置变化带来的语义变化。
• 第三，尝试用栈和递归各写一遍，然后对比三者代码量、出错概率和空间占用。

这三件事做完，这道题才算真正内化成了你自己的东西。遇到面试官进一步追问时，你聊得出来的往往不是答案本身，而是你对这个问题的思考过程，这恰恰是高价岗位面试中最值钱的部分。