企业官网建设流程全解析

刷 LeetCode 的朋友对第 19 题不会陌生：删除链表的倒数第 N 个结点。这个题被划在“链表中级”一档，但真动手写的时候，很多人第一反应是先遍历一遍拿到链表长度，再走一遍去删目标节点。这种做法当然没问题，但如果面试官追问一句“能不能只遍历一次？”，思路就得换成双指针。这篇文章就从这道题出发，把双指针一次遍历的来龙去脉、手写细节、边界条件和容易踩的坑一次说清楚。题目不长，但背后藏着的思考方式，能帮你打通不少链表题目。

1. 题目到底在考什么：先看懂暴力解法和双指针的意图

1.1 题目描述和最容易想到的两遍扫描

题目说的是给一个单链表，给定整数 n，删除从链表尾部数的第 n 个节点，然后返回头节点。比如链表1 -> 2 -> 3 -> 4 -> 5，n = 2，删除的是 4，最后返回1 -> 2 -> 3 -> 5。

最直观的思路是：先扫一遍链表，数出长度 L，然后知道倒数第 n 个节点就是正数第 L - n + 1 个节点，要删它就要找到它的前驱，也就是第 L - n 个节点。走到那里，把prev->next = prev->next->next一改，完事。

这个思路没有任何问题，复杂度是 O(L) 时间，O(1) 空间。但问题在于它遍历了两遍：一遍数长度，一遍走删除。面试如果只是让你做出来，这可能够了；但如果面试官强调“你能否只扫描一趟完成删除”，你就需要把思路切换到双指针上。

1.2 为什么“倒数第 N 个”天然适合双指针

链表这个东西和数组不一样，它没有随机访问，你不知道当前节点是第几个，更不知道距离尾部还有多远。想一次遍历就定位倒数第 n 个节点，最自然的办法就是制造一个长度差。

你可以想象两个人赛跑：一个跑得快，一个跑得慢。先让快的人提前跑 n 步，然后两个人保持同样的速度一起前进。等快的人跑到终点（链表末尾的 null）时，慢的人和快的人之间的距离始终是 n 步，所以慢的人刚好站在倒数第 n 个节点的位置上。这就是双指针法最核心的思想。

不过这里有一个关键的细节：删除节点需要知道它的前驱节点。如果慢指针正好停在倒数第 n 个节点上，你是没法直接删掉它的——你只能拿到这个节点本身，无法访问它前面的节点。所以在实现的时候，我会让慢指针停在倒数第 n + 1 个节点（也就是待删节点的前驱）上，这就需要一个虚拟头节点的帮忙。

提示：链表的删除操作，本质上是在改某个节点的 next 指针。如果待删节点是头节点，你没有前驱可用，所以统一用虚拟头节点dummy处理，能省去一堆 if 判断。

2. 双指针核心原理：快指针先走 N 步，慢指针负责停在目标前驱

2.1 一次遍历的精髓：制造长度差

我直接讲最常用的实现方式，也是官方题解里的版本：

1. 创建一个虚拟头节点dummy，让dummy.next = head。
2. 定义快指针fast和慢指针slow。我习惯让fast从真正的头节点出发，让slow从dummy出发。
3. 让fast先走 n 步。
4. 然后让fast和slow一起走，每次各走一步，直到fast走到 null。
5. 此时slow.next就是倒数第 n 个节点，执行slow.next = slow.next.next完成删除。
6. 返回dummy.next。

为什么slow初始指向dummy，而不是head？因为我们要让最终停顿点落在待删节点的前驱上。

我画一个演示过程，链表是dummy -> 1 -> 2 -> 3 -> 4 -> 5，假设 n = 2：

初始：fast = 1，slow = dummy 第一步：fast 先走 2 步，到 3 然后同时走： fast 到 4，slow 到 1 fast 到 5，slow 到 2 fast 到 null，slow 到 3

此时 slow 指向 3，3 是倒数第 2 个节点 4 的前驱，所以执行slow.next = slow.next.next，就把 4 删掉了。整个过程中，快指针扫了一遍链表，慢指针跟着扫了一遍，两者一共走了大约 L 步，而不是 L 遍，因此是真正的一次遍历。

2.2 快指针走 N 步还是 N+1 步？这里最容易混

我看过不少人的笔记，发现大家卡得最多的点是：为什么有的写法里fast先走 n 步，有的写法里先走 n + 1 步？

这和slow的初始位置是配套的。我说一个通用的判断方法：关键看你想让最终slow停在哪。

• 如果fast初始在head，slow初始在dummy，那么fast先走 n 步之后，两者之间已经隔着 n 个“距离”。一起走时，fast到 null 时slow距离 null 还有 n 步，所以它指向倒数第 n + 1 个节点，即待删节点前驱。
• 如果fast和slow都初始在dummy，那你必须让fast先走 n + 1 步，也就是比待删节点多走一步，这样slow才能刚好落在前驱上。
• 如果fast和slow都初始在head，fast先走 n 步，那么fast到 null 时slow停在倒数第 n 个节点上，这是目标节点本身，不是前驱，删除时会很尴尬。

所以你可以发现，不同的初始位置对应不同的步数，没有唯一的“标准答案”。但面试时最好固定一种写法，我自己的习惯就是第 2.1 节那套，思路最不容易乱。

注意：无论怎么写，快指针先走的那几步不计入“共同遍历”的过程。整段操作里，链表最多被从头到尾访问一次，空间上只有两个指针，O(1)。

3. 代码实现：Python 和 C++ 双版本逐行拆解

3.1 Python 实现：简洁直接

如果你用 Python 刷题，下面这段可以原样跑通：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def removeNthFromEnd(head: ListNode, n: int) -> ListNode: dummy = ListNode(0, head) fast = head slow = dummy # fast 先走 n 步 for _ in range(n): if fast is None: return head # 链表长度不够 n，题目通常保证 n 有效，防御用 fast = fast.next # 两个指针一起走到 fast 为 None while fast: fast = fast.next slow = slow.next # slow.next 就是要删的节点 slow.next = slow.next.next return dummy.next

这段代码的核心就三步：走 n 步、同步走、改 next。需要注意，Python 里ListNode(0, head)这种写法依赖构造函数的第二个参数，如果你用的是 LeetCode 默认的ListNode类，它的构造函数本身支持ListNode(val=0, next=None)，所以没问题。

我在代码里加了一个防御判断：如果fast还没走满 n 步就变成None，说明链表长度不足 n，题目输入不会出现这种情况，但你写给自己项目里的通用工具函数时，这种保护能让函数更健壮。如果不加，fast为None后还要执行fast.next，会直接抛空指针异常。

3.2 C++ 实现：注意内存释放

C++ 版本和 Python 逻辑完全一样，但多了手动管理内存这一步：

struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(0, head); ListNode* fast = head; ListNode* slow = dummy; // fast 先走 n 步 for (int i = 0; i < n; ++i) { if (fast == nullptr) { // 题目保证 n 合法，这里只是为了防御 return head; } fast = fast->next; } // 同步移动 while (fast != nullptr) { fast = fast->next; slow = slow->next; } // 删除节点 ListNode* target = slow->next; slow->next = slow->next->next; delete target; // 返回新头，并释放虚拟头节点 ListNode* newHead = dummy->next; delete dummy; return newHead; }

为什么 C++ 里slow->next = slow->next->next之前要单独保存target？因为一旦修改了slow->next，原来那个节点的指针就不容易拿到了，不保存直接改，后面就没法delete，会造成内存泄漏。刷题时 LeetCode 不会盯着你内存泄漏，但面试里如果要求写完整 C++，这属于基本功。

3.3 边界条件与防御性写法

边界条件永远是链表题的命门。我总结一下这段代码处理三种情况的机制：

第一，删除的是头节点。比如链表1 -> 2，n = 2，要删 1。按代码流程，fast走 2 步后正好变成null，slow还在dummy，while循环一次都不会进，slow->next就是原来的头节点 1，执行删除后返回dummy->next，也就是新的头节点 2。这一步如果没有dummy，要单独处理“删除头节点”的情况，很容易漏。

第二，n 等于链表长度。这种情况等价于删除头节点，上面已经覆盖了。

第三，链表长度为 1，n = 1。fast走 1 步后为null，slow在dummy，删除dummy->next，返回null。逻辑依然成立。

所以虚拟头节点最大的意义就是让“头节点”和“普通节点”的删除逻辑完全统一，不用在代码里写一个if (head == null || n == 1)的旁路分支。

4. 实操中的坑：从“报错”到“一次过”

4.1 很容易翻车的三个边界细节

第一，指针初始位置搞错。我见过很多人把slow也初始化为head，结果删不掉目标节点，或者删了错误的节点。你要记住：slow必须落后fast足够的距离，并且要落在前驱上。最简单的方法就是照着第 2.1 节的初始化来，不要随意改。

第二，循环结束条件的判断。有些版本会写while (fast->next != nullptr)，这时快指针走到最后一个节点就停了，slow的位置会差一个节点。和前面的步数选择是对应的，但没有统一的推导就很容易出错。我的建议是直接以fast == null作为结束条件，和“快指针到达终点”的概念一一对应。

第三，没有处理空链表或 n 非法。普通项目里如果输入 n 大于链表长度，你没保护就会直接段错误。我建议在“快指针先走 n 步”的循环里加一个空指针判断，这样对异常输入也能安全退出。

4.2 常见问题排查速查表

我在实战中把容易踩的坑整理成了一张表，写代码之前可以对照看一眼：

这张表不是背的，是写错之后对着调试用的。我当时第一次提交就挂在“删了头节点返回了原 head”上，因为没建 dummy，后来换成虚拟头节点，一次过。

5. 举一反三：双指针在链表题里的其他战场

5.1 寻找链表中点：一快一慢，速度不同

链表中点也是一道高频面试题。思路是slow每次走一步，fast每次走两步，当fast到达末尾时，slow正好在中点。代码非常简单：

def middleNode(head: ListNode) -> ListNode: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow

这和删除倒数第 N 个节点的思路同源，都是快慢指针制造“路程差”。你做熟了这道题，再看中点问题会感觉非常亲切。

5.2 判断链表是否有环：快慢指针相遇

判断链表有没有环，另一个经典应用。如果有环，fast进入环之后迟早会追上slow，两人相遇就是有环；如果fast走到 null，就是无环。

def hasCycle(head: ListNode) -> bool: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: return True return False

我之前刷题的时候，第 19 题、876 题、141 题连着做，发现它们全是同一套双指针思想，只是速度差和起点不同而已。

5.3 从这道题延伸出的思维模型

如果你把“删除倒数第 N 个结点”想通了，你应该有能力自己推导很多变体：

• 删除链表的中间节点：先找中点，再删，两个指针就能搞定。
• 求倒数第 N 个节点：不删除，只返回节点，那就让slow直接停在目标节点上，快指针先走 n 步后同步走，fast到 null 时slow就是答案。
• 旋转链表右移 k 位：本质也是快指针先走 k 步，然后快慢一起走，找到新头的前驱。

这些都是同一种“先制造长度差，再同步推进”的模型。所以我特别建议你把第 19 题当作双指针入门的第一课，思路通了，后面会轻松很多。

5.4 为什么不用栈或递归

也许有人会问，一次遍历也能用栈：先全部压栈，再弹出 n 个，弹到第 n 个时删除。或者用递归，回溯时计数。这两种方式当然也能实现，但需要 O(n) 的额外空间。双指针只需要两个指针节点，空间 O(1)。在链表题里，空间复杂度往往和面试官出题意图直接挂钩，遇到“能否只扫描一次”这种限制时，双指针才是符合题意的答案。

我刚才重新写了一遍完整的 C++ 版本，在本地加了几个测试用例跑了一遍，包括链表长度为 1、n = 1，删头节点，以及正常删除中间节点。kena感觉最稳的还是哑节点那套写法，逻辑统一，不容易改错。这道题代码不到二十行，但你要真的吃透它的指针位置推导，而不是死记“fast 先走 n 步”，否则面试官换个初始条件把你一问，你很容易露馅。下次再看到链表题，可以先想想能不能用快慢双指针制造距离差，很多看起来绕的问题，其实就是多走几步的距离差问题。