企业官网建设流程全解析

上个周末我帮一个朋友做模拟面试，随手挑了LeetCode 19这道删除链表倒数第 N 个结点的题。他面过这道题，上来就写了快慢指针，代码格式和命名都很规范，可我问了一句“为什么 fast 要先走 n+1 步，slow 要从 dummy 出发，而不是从 head 出发”，他愣了半天，最后承认自己是背的模板。这道题在 LeetCode 上常见的主流思路一共有三类：长度法、快慢指针、栈；表面是三种写法，内里全是链表题最经典的差一问题。如果你正准备面试，或者刚开始刷链表题，这篇内容想把三种解法的原理、代码、边界和踩坑经验一次讲清楚。

我当时追问他三个问题：链表长度怎么求？倒数第 N 个结点的“前驱”是谁？如果删的是头结点怎么办？这三个问题答明白，这道题才算真正会了。下面不绕弯子，直接从头开始拆。

1. 先看题：倒数第 N 个，天然就是单向链表的陷阱

1.1 题面回顾与“倒数”的本质

题目描述非常简单：给定一个单链表 head，删除倒数第 n 个结点，返回头结点。n 是有效值，也就是 1 ≤ n ≤ 链表长度。这个“有效”条件很重要，它省去了很多边界校验的啰嗦，但并没有省去我们对边界条件的思考。

单链表的结构决定了它只能从 head 一路 next 往后走，不能回头看。数组里你要删倒数第 n 个元素，直接算下标 arr.length - n 就行；链表不行，因为链表的“下标”和内存位置没有随机访问能力。倒数第 n 个，翻译成正数就是第 L - n + 1 个（L 为链表长度）。要删的是这个节点本身，可单链表删除的实质是修改前驱节点的 next，所以你真正要找的是第 L - n 个节点，也就是待删节点的前驱。

这个“正数是第几个”和“要操作哪个指针”之间，就是差一问题开始的地方。很多人写错，不是代码能力不行，而是没有意识到删除操作和查找操作的目标不一样。

1.2 dummy 节点不是技巧，是删除头结点时唯一体面的方式

当待删节点恰好是头结点时，它没有前驱。这时候常规的prev->next = target->next根本写不出来，因为 prev 不存在。新手最常见的处理是单独写一个 if 判断是不是头结点，再分两条路走。我不是说这样不行，而是这样的代码分支多，边界容易漏。

更干净的做法是新建一个哑节点 dummy，让 dummy->next 指向 head。不管要删的是头结点还是中间节点，在逻辑上 dummy 都充当 head 的前驱。最后返回 dummy->next 即可。用这个技巧，三种解法都能把“删除头结点”和“删除普通节点”统一成同一段逻辑。

我之前帮人 code review 时见过一个反面案例：他用了 dummy 之后还在代码里单独判断if (n == length) head = head->next;，看起来小心翼翼，实际完全多余。记住这一条——只要加了 dummy，就不要单独处理头结点。

2. 解法一：长度法——先数清楚，再动手

2.1 思路与代码：两次遍历，把倒数换算成正数

长度法的思路最直白：先完整遍历一次链表，数出总长度 L。然后倒数第 n 个就是正数第 L - n + 1 个，删除它需要拿到第 L - n 个节点作前驱，于是从 dummy 出发，走 L - n 步就能停在待删节点的前驱上。

ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(0, head); int length = 0; ListNode* cur = head; while (cur) { ++length; cur = cur->next; } // 从 dummy 出发走 length - n 步，停在待删节点的前驱 ListNode* prev = dummy; for (int i = 0; i < length - n; ++i) { prev = prev->next; } ListNode* target = prev->next; prev->next = target->next; delete target; ListNode* newHead = dummy->next; delete dummy; return newHead; }

举个例子，链表是 1 -> 2 -> 3 -> 4 -> 5，n = 2。L = 5，length - n = 3。dummy 是第 0 个位置，走 3 步到节点 3，节点 3 正是倒数第 2 个节点也就是节点 4 的前驱。然后prev->next = target->next就把 3 的 next 从 4 改到 5 了。

这里的推导值得稍微展开一下。倒数第 n 个节点是正数第 L - n + 1 个，它的前驱是正数第 L - n 个。dummy 位于所有节点之前，算第 0 个，所以从 dummy 出发走 L - n 步，恰好到达第 L - n 个节点。每一步都是朴素的 next 移动，不需要再做加法减法。

2.2 长度法的三个容易写错的地方

第一，统计长度时用while (cur)而不是while (cur->next)。前者走到 nullptr 才停，length 正好是节点个数；后者虽然也能数出长度，但在空链表上会直接解引用空指针。LeetCode 的测试用例很少给空链表，但本地测试时你一定会踩到。

第二，第二个循环的边界是i < length - n，不是i <= length - n。多加一个等号，prev 就从“前驱”变成“待删节点”，后面删除时你还得再记一个更前面的节点，代码瞬间就从两行变成五行。

第三，最终必须返回dummy->next，不能图省事返回 head。当 n 等于链表长度时，head 就是被删除的那个节点，代码里已经delete target了，再返回 head 就是返回一个悬空指针，本地跑起来程序直接崩。

2.3 什么时候长度法并不差

很多文章把长度法叫“笨办法”，我不太同意。在 LeetCode 这种判断题里，它确实多遍历了一次，可实际工程里链表经常会自带长度字段，比如标准库的 LinkedList 都有 size() 接口。如果链表类本身维护了 size，长度法实际上就是一次遍历，时间复杂度低，逻辑也最好懂。

即便没有 size 字段，长度法在面试中也很有价值：它是你能最快写出、最不容易出错的思路。面试时你可以先给长度法，证明你会分析问题，然后主动说“如果面试官要求一次遍历，我还有优化方案”，这比一上来就甩一个快慢指针模板要自然得多。

3. 解法二：快慢指针——一次遍历的真相与边界细节

3.1 关键设计：为什么 fast 要先走 n+1 步

快慢指针的代码识别度很高，但真正理解它的人并不多。设计是这样的：fast、slow 都从 dummy 出发，fast 先走 n+1 步，然后 fast 和 slow 一起每次走一步。当 fast 到达 nullptr 时，slow 停的位置恰好是待删节点的前驱。

核心问题来了：为什么是 n+1，不是 n？假设 fast 只先走 n 步，两指针之间拉开的距离是 n 个节点。fast 到末尾时，slow 与末尾之间也隔着 n 个节点，所以 slow 正好指向待删节点本身。可删除需要的是前驱，你后面还得补一个变量记住 slow 前面的节点，或者用ListNode* tmp = slow->next; slow->next = slow->next->next之类的写法，虽然也能删，但通用性差一些。

让 fast 先走 n+1 步，slow 和 fast 之间保持 n+1 个节点的距离。fast 到 nullptr 时，slow 和末尾之间隔着 n+1 个节点位置，也就是说 slow 是倒数第 n+1 个节点，刚好是倒数第 n 个节点的前驱。之所以能从 dummy 出发，是因为 dummy 在 head 前面补了一个位置，让“删除头结点”也变成普通情况。

ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(0, head); ListNode* fast = dummy; ListNode* slow = dummy; // fast 先走 n+1 步 for (int i = 0; i <= n; ++i) { fast = fast->next; } // 然后同步走 while (fast != nullptr) { fast = fast->next; slow = slow->next; } ListNode* target = slow->next; slow->next = target->next; delete target; ListNode* newHead = dummy->next; delete dummy; return newHead; }

3.2 指针移动轨迹推演

光讲概念不够，我建议你自己在纸上走一遍。拿 1 -> 2 -> 3 -> 4 -> 5，n = 2 为例。

fast 先走 3 步，从 dummy 走到节点 3，slow 还在 dummy。接下来进入 while 循环：

• 第 1 轮：fast 从 3 走到 4，slow 从 dummy 走到 1
• 第 2 轮：fast 从 4 走到 5，slow 从 1 走到 2
• 第 3 轮：fast 从 5 走到 nullptr，slow 从 2 走到 3

此时 fast 是 nullptr，循环结束，slow 正好在节点 3，slow->next就是待删的节点 4。这个走位非常规整，但如果你把 fast 先走 n 步，同样的链表，最终 slow 会停在节点 4 本身，多出来的那一步就是天壤之别。

还有一种常见写法是 fast 先走 n 步，然后让 slow 从 dummy 出发，fast 走到最后一个节点（fast->next == nullptr）时停止，slow 恰好也是停在待删节点的前驱。这种写法也能跑通，但我个人不推荐混搭，因为“fast 先走 n+1 步 + 循环条件 while(fast)”是一套自洽的组合，改变任何一个，位置都会偏差。

3.3 面试追问：“你能一次遍历吗？”背后的考察点

面试官让你优化成一次遍历，考察的不是记忆力，而是你有没有真正理解“用距离差模拟倒数”的思想。所以回答快慢指针时，主动说出这几件事：fast 和 slow 为什么要保持 n+1 的距离、dummy 的作用是什么、循环终止条件为什么用while (fast != nullptr)。

如果面试官进一步问“链表能不能真的从后往前走”，你可以顺势说单链表没有反向引用，所以只能用这种“先发射一个探针，再让慢指针跟随”的思路。这本质上是一种延迟执行，现实里也有对应场景，比如接收数据流时要等缓冲区积攒到一定长度再处理，模式类似。

空间上，快慢指针只用了两个额外指针，是 O(1)；时间复杂度 O(L)，每个节点最多被 fast 访问一次，slow 再访问一次，严格说常数是 2，但大 O 就是 O(L)。

4. 解法三：栈——用空间换一种直白的思考方式

4.1 把“倒数”翻译成“先进后出”

快慢指针用物理距离模拟倒数，栈则用先进后出的特性天然处理倒数。你只需要做两件事：先把链表从头到尾压入栈，然后从栈顶弹出 n 个节点。第 n 次弹出的节点就是待删节点，弹出后新的栈顶恰好是它的前驱。

这个解法我第一次见时觉得有点“绕”，但后来想通了：栈把“遍历方向”完全反转了，链表从头到尾入栈，栈顶就是链表尾。倒数第 n 个节点相当于正数第 n 次从栈顶弹出。算法题里当你要从尾到头处理数据时，栈往往是最直接的数据结构。

这里的 dummy 依然有必要。如果栈里没有 dummy，删除头结点时，弹出 n 次后栈可能已经空了，取前驱就成了空栈操作。让 dummy 最先入栈垫底，既保证了删除头结点时前驱存在，又统一了代码逻辑。

4.2 C++ 实现与内存语义

ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(0, head); stack<ListNode*> st; ListNode* cur = dummy; while (cur) { st.push(cur); cur = cur->next; } ListNode* target = nullptr; for (int i = 0; i < n; ++i) { target = st.top(); st.pop(); } ListNode* prev = st.top(); // 栈里一定有 dummy，所以不会空 prev->next = target->next; delete target; ListNode* newHead = dummy->next; delete dummy; return newHead; }

注意栈里存的是ListNode*指针，不是 int 值。如果你写成stack<ListNode>，每次 push 都会复制一整个节点，浪费空间还改变了指针关系。这种对象拷贝的错误很隐蔽，编译器不会报错，但内存占用和逻辑都会出问题。

空间复杂度是 O(L)，因为在极端情况下整个链表都会进栈。在 n 很小的时候确实浪费，但它的优势是语义直白、几乎不需要理解快慢指针的那种“距离差”技巧。面试场景下，如果你前面已经讲了长度法和快慢指针，再补一句“用栈也能做”，会显得你掌握的不是一个孤立模板，而是一整套解决问题的工具箱。

4.3 栈解法的工程启发

栈解法看起来只是“多了一种思路”，但它在实际工程里的对应场景很常见。举个例子，编辑器的撤销功能，你要撤销最近一次操作，本质就是把操作记录压栈，然后从栈顶弹出回滚；编译器检查括号匹配，也是把左括号压栈，遇到右括号弹栈。

这道题用栈做确实不是最优空间解，但它揭示了“数据结构的先进后出特性可以扭转遍历顺序”这一思想。当你以后遇到需要倒序处理线性数据的业务，比如日志倒查、导航回退，可以第一时间想到栈，这就是刷这道题收获的一部分。

5. 三种解法横评：笔试、面试、工程，怎么选

5.1 复杂度对照表

从复杂度看，长度法和快慢指针的空间都是 O(1)，区别只在是否允许遍历两次。实际工程里如果链表自带 size，长度法反而最推荐；如果是 LeetCode 面试题，快慢指针最稳妥；栈解法适合作为补充答案展示思维宽度。

5.2 面试回答顺序与复盘要点

我自己做面试官的时候，最反感候选人一句话不说直接默写快慢指针。不是说快慢指针不对，而是它太像“背题”。更好的回答节奏是：先从长度法讲起，讲清楚求长度、换算正数、找前驱这一整套逻辑；然后主动优化，“题目要求一次遍历的话，可以用快慢指针，让 fast 先走 n+1 步……”；如果面试官有兴趣，再补栈解法。

面试结束后的复盘，重点看三件事：

• 是否理解 dummy 存在的意义；
• 是否能解释 fast 为什么走 n+1 步；
• 是否能准确说出循环终止条件。

这三个问题能答清楚，就算代码写得慢一点，面试官也会觉得你是真的会，而不是背下来的。很多候选人背了模板，一换数字就不会了，就是栽在这上面。

6. 实战排坑：刷完这道题之后，我总结的四个细节

6.1 坑一：返回旧 head 而不是 dummy->next

我见过有人明明新建了 dummy，最后却写return head;。这代码在大部分测试用例里都能过，唯独 n 等于链表长度时会出问题：head 指向的节点已经被 delete，你返回的是一个悬空指针。C++ 里这个行为是未定义的，本地可能崩，也可能碰巧跑出随机值，线上就更不可控。

正确姿势永远是ListNode* newHead = dummy->next;，然后再 delete dummy。注意顺序：先取 newHead，再释放 dummy，这两个操作互不影响，因为 newHead 是 dummy 所指向的下一个节点，释放 dummy 不会带走它。

6.2 坑二：本地构造链表时，没有配套的释放逻辑

LeetCode 的判题环境不检查内存泄漏，但本地调试时如果不释放，用 Valgrind 或 AddressSanitizer 一跑就是满屏报错。我刷链表题的习惯是写三个辅助函数：createList、printList、freeList，专门用来做本地验证。

ListNode* createList(const vector<int>& nums) { ListNode* dummy = new ListNode(0); ListNode* cur = dummy; for (int num : nums) { cur->next = new ListNode(num); cur = cur->next; } return dummy->next; } void printList(ListNode* head) { while (head) { cout << head->val << " -> "; head = head->next; } cout << "nullptr" << endl; } void freeList(ListNode* head) { while (head) { ListNode* next = head->next; delete head; head = next; } }

有了这套辅助函数，你可以针对 n=1、n=L、L=1 三种边界反复测，既验证算法正确性，也让自己真正意识到“删除节点要释放内存”不是一个可有可无的动作。

6.3 坑三：长度法第二个循环的差一问题

长度法最常见的问题出现在第二个循环。如果从 head 出发，很多人会写for (int i = 1; i < length - n + 1; ++i)，这个循环结束之后，cur 停在待删节点本身，而不是它的前驱。于是你不得不额外加一个变量来记录上一个节点，代码瞬间变得复杂。

我推荐始终从 dummy 出发，循环变量从 0 开始，循环次数是 length - n。这背后的逻辑是：dummy 占第 0 个位置，走 length - n 次正好到达第 length - n 个节点，也就是待删节点的前驱。每次循环只做prev = prev->next，不掺杂任何判断，思路最干净。

6.4 坑四：快慢指针的循环条件想当然

快慢指针的另一个高频错误是把while (fast != nullptr)写成while (fast->next != nullptr)。乍一看，后者似乎是让 fast 停在最后一个节点，不再往后多走一步；但当你让 fast 先走 n+1 步之后，如果链表长度恰好是 n，fast 已经是 nullptr，再判断fast->next就会解引用空指针，直接崩溃。

即便链表长度大于 n，while (fast->next)会让 fast 提前一个位置停止，slow 跟着少走一步，最终指向待删节点而不是前驱，删除逻辑还是错的。我把结论说直白一点：fast 先走 n+1 步，循环条件就用while (fast != nullptr)，这是一对固定搭配，不要混搭。

这道题我这几年陆陆续续刷过很多遍，每次重新写都会发现自己的指针感又退步了一点。后来我总结出一个习惯：写代码前先问自己三个问题——链表长度是多少？我要删的节点的前驱是谁？删的是头结点怎么办？这三个问题想清楚，长度法、快慢指针、栈的代码几乎都是水到渠成。希望这篇分析能帮你把这道经典题的差一逻辑真正刻进肌肉记忆，下次再遇到链表删除，能少踩一个是一个。