企业官网建设流程全解析

“删除链表的倒数第 n 个结点”，是我自己面试别人时必问的一道链表题。它看起来简单，实际上把链表操作里最容易被忽视的三件事全占了：边界条件、前驱查找、指针悬挂。很多候选人第一次写都能“跑通”，但你追问一句“为什么 first 走 n 步之后，second 正好停在待删结点的前一个位置”，他就会沉默。这就说明代码是背的，不是理解的。

先说结论：这道题最推荐的解法是“双指针 + 虚拟头结点”。虚拟头结点可以消除“删除头结点”这个特殊分支，双指针可以让查找过程只遍历一次。下面不打算只贴一段答案，而是从最朴素的“两遍扫描”开始，把为什么优化、怎么优化、边界怎么验证、代码怎么写、工程里要注意什么，一层层说清楚。这篇文章适合正在刷链表题准备面试的人，也适合工作中自己封装链表、被野指针和空指针折磨过的开发者。

1. 先看清这个题：它在考察什么

1.1 题目到底说了什么

输入是一个单链表和一个整数 n，要求删除从链表末尾数起的第 n 个结点，返回删除后的链表头结点。举个例子，链表是 1 -> 2 -> 3 -> 4 -> 5，n = 2，倒数第 2 个结点是 4，删除后链表变成 1 -> 2 -> 3 -> 5。

题目本身没有任何歧义，但它的坑都藏在“倒数”和“删除”这两个词里。“倒数”意味着你不知道链表有多长，除非先遍历一遍；“删除”意味着单链表的删除必须找到被删结点的前驱，而不是被删结点本身。这两个限制叠加在一起，就是这道题真正的难度来源。

很多人在初学阶段会先想到最直接的办法：先遍历链表数出长度 L，那么倒数第 n 个结点就是正数第 L - n + 1 个结点，再走一遍链表，找到它的前驱，执行删除。这个思路完全正确，也能通过绝大部分测试用例，但它需要遍历两遍链表。面试官通常不会就此罢休，而是会问：能不能只遍历一遍？

1.2 最容易忽略的三种边界

这种题的边界条件，比主逻辑更值得写进笔记。

第一种，删除的是头结点。如果 n 正好等于链表长度，那倒数第 n 个就是头结点。没有做特殊处理的话，删除头结点之后需要手动更新 head，这一步很容易漏掉。

第二种，删除的是尾结点。当 n = 1 时，需要删除链表的最后一个结点，此时前驱是倒数第二个结点，如果链表只有一个结点，前驱就是空的，处理起来又是特殊情况。

第三种，链表只有一个结点且 n = 1。删除之后链表为空，返回的应该是空指针。

很多代码在 LeetCode 上提交失败，问题基本都出在这三种情况上。这也是为什么我强烈建议用一个“虚拟头结点”把边界拉平，后面会详细说。

1.3 两种思路的对比：两遍扫描与双指针

两遍扫描的思路很朴素：先求长度，再走 L - n 步找到前驱，执行删除。它的优点是直观、不容易错，缺点是必须完整遍历两遍，而且第一遍遍历除了求长度之外没有任何产出。

双指针的思路则是让查找前驱的过程和链表末端对齐。先让一个指针 first 从虚拟头结点出发往前走 n 步，另一个指针 second 停在虚拟头结点，然后两个指针同步前进。当 first 走到链表末尾时，second 正好落在被删结点的前驱位置。

我用一个表格对比这两种做法：

表面上看，两种解法的时间复杂度都是 O(L)，常数上的差别不算大。但双指针在面试中更受认可，因为它体现的是“如何让两个指针的相对距离成为解题工具”这一思想，这个思想在后面做链表成环检测、找中间结点、合并有序链表时都会反复出现。而且双指针配合虚拟头结点，写出来的代码比两遍扫描更容易做到“无分支处理头结点”的优雅状态。

2. 双指针解法的原理拆解

2.1 指针之间为什么差 n 步

先说核心结论：两个指针都从虚拟头结点出发，first 先走 n 步，然后 first 和 second 同步一次走一步，直到 first 到达链表末尾。此时 second 指向的结点，正好是要删除结点的前驱。

这个结论可以用生活中的例子来理解：两个人站在同一条跑道上，first 提前跑了 n 步，然后两个人以相同的速度一起跑。只要 first 不停下来，两个人之间的距离永远保持 n 步。当 first 到达终点线时，second 距离终点线也正好是 n 步。放到链表里，“终点线”就是链表最后一个结点，“距离终点线 n 步”的位置，正是倒数第 n 个结点的前驱。

为什么强调“前驱”而不是“被删结点”？因为单链表删除操作的唯一手段，就是让前驱结点的 next 跳过被删结点，指向被删结点的后继。如果你只拿到了被删结点本身，在单链表里你是无法拿到它的前驱的，只能再从头遍历一次。所以双指针真正做的事情，不是“找到被删结点”，而是“在被删结点出现前就停在它的前驱上”。

有人会问：让 first 先走 n+1 步行不行？当然可以。如果 first 先走 n+1 步，那么当 first 到达 NULL 时，second 正好指向被删结点的前驱。这两种写法本质一样，只是判断终点的方式不同：走 n 步时要用first->next == NULL作为停止条件；走 n+1 步时用first == NULL作为停止条件。我的习惯是走 n 步，因为“先走 n 步”这句话在面试时更容易讲清楚。

2.2 虚拟头结点到底解决了什么

虚拟头结点，也叫哨兵结点，是一个不存储有效数据的额外结点，它的 next 指向真正的链表头。执行删除时，我们不直接操作 head，而是统一操作“某个结点的 next”，最后再通过dummy->next拿到新的头结点。

这样做最大的好处是：当被删结点是头结点时，不需要写head = head->next这种特殊分支。比如链表只有 1 个结点，n = 1，如果不加虚拟头结点，你要判断 head 为空然后返回空指针；加了虚拟头结点之后，p 指向虚拟头结点，执行p->next = p->next->next，虚拟头结点的 next 变成了 NULL，再返回dummy->next，一切顺理成章。

可以对比一下没有虚拟头结点的代码。你需要判断“second 是否指向头结点前驱”，也就是删除头结点时，删完之后 head 要往后移。这个分支很容易忘记，而且一旦忘记，测试用例里只要出现 n 等于链表长度，程序就会返回错误的链表头。

所以我的建议是：只要题目涉及“删除链表结点”，不管你用什么思路，先加一个虚拟头结点再说。它不会增加任何时间或空间复杂度，只需要额外创建一个结点，就把一类边界问题整个消灭掉。

2.3 参考代码：C语言实现与Python实现

先看 C 语言版本。这里假设结点结构已经定义好：

#include <stdlib.h> struct ListNode { int val; struct ListNode *next; }; struct ListNode* removeNthFromEnd(struct ListNode* head, int n) { // 创建虚拟头结点 struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode)); dummy->next = head; // first 和 second 都从虚拟头结点出发 struct ListNode* first = dummy; struct ListNode* second = dummy; // first 先走 n 步 for (int i = 0; i < n; i++) { first = first->next; } // 两个指针同步走，直到 first 指向最后一个结点 while (first->next != NULL) { first = first->next; second = second->next; } // 此时 second 指向待删结点的前驱 struct ListNode* toDelete = second->next; second->next = toDelete->next; free(toDelete); // 取新的头结点，并释放虚拟头结点 head = dummy->next; free(dummy); return head; }

Python 版本更简洁，因为不需要考虑手动释放内存的问题：

def remove_nth_from_end(head, n): dummy = ListNode(0) dummy.next = head first = dummy second = dummy for _ in range(n): first = first.next while first.next: first = first.next second = second.next second.next = second.next.next return dummy.next

两个版本的核心逻辑一致。C 语言版本里我特意加了free(toDelete)和free(dummy)，因为在真实工程里，这两行少一个，程序运行几次之后内存就会持续上涨。面试手写代码时如果用的是 C/C++，可以主动说出来“删除的结点我会释放内存”，这通常是一个加分细节。

3. 边界验证与复杂度分析

3.1 用具体链表逐条跑边界

写完代码别急着提交，先在脑子里拿几个典型用例走一遍。

链表 1 -> 2 -> 3 -> 4 -> 5，n = 2。dummy 在链表前，first 走 2 步到结点 2，second 在 dummy。同步走，当 first 到结点 5 时，second 到结点 3。删除 second->next，也就是结点 4，链表变成 1 -> 2 -> 3 -> 5。

链表 1 -> 2 -> 3，n = 3。first 走 3 步到结点 3，同步走，当 first 到结点 3（最后一个）时，second 还在 dummy？不对，初始 first 走到结点3，second 在 dummy，此时 first->next 不是 NULL（因为结点3有后继？如果没有的话），如果链表长度为3，n=3，first 走3步，从 dummy 到结点1、结点2、结点3？我先理清：dummy 是位置0，first 走第1步到结点1，第2步到结点2，第3步到结点3。然后 while (first->next != NULL)，结点3的next是NULL，所以while循环直接不执行。second 仍在 dummy。删除 second->next 即结点1。正确。

链表只有一个结点，n=1。dummy->next = 结点1。first 走1步到结点1，while条件 first->next != NULL 为假，second不动。second 是 dummy，删除 dummy->next，链表变空，返回 dummy->next 即 NULL。正确。

以上三种情况，恰好对应了最容易出错的“删除中间结点、删除头结点、删除后链表为空”三类场景。用了虚拟头结点之后，代码路径完全一致，不需要任何 if 判断，这就是这个设计的价值所在。

3.2 时间复杂度为什么是 O(L)

这段看起来简单，但很多人被面试官追问时说不清楚。

L 是链表长度。双指针的解体中，first 先走 n 步，这个循环最多执行 n 次。然后 first 和 second 一起走，直到 first 走到最后一个结点，这段距离是 L - n 步。总步数是 n + (L - n) = L。所以整个算法对链表只完整遍历了一遍。

空间复杂度是 O(1)，因为我们只额外创建了一个虚拟头结点，以及两个指针变量。这个复杂度无论 n 怎么变都是固定的。

对比一下两遍扫描的做法：第一遍求长度走 L 步，第二遍找前驱走 L - n 步，总步数接近 2L。虽然时间复杂度同样是 O(L)，但实际执行步数是双指针解法的两倍。如果面试官问“双指针到底优化了什么”，准确回答是：它把常数时间从 2L 降到了 L，并且顺带把边界处理做得更统一。

3.3 题目没说的话：n 非法时怎么办

LeetCode 原题会保证 n 一定合法，也就是说 n 不会小于 1，也不会大于链表长度。但工程里没有“输入保证”这回事，如果别人调用你的函数时传了一个非法 n，你的代码不能崩。

处理方式很简单：first 先走 n 步时，如果中途就遇到了 NULL，说明 n 已经超过链表长度，这时候直接返回原来的 head 即可。在 C 语言版本里，进入 for 循环前可以先判断 n 是否小于等于 0；如果 first 在循环过程中变为 NULL，同样直接返回。

这里有一个容易踩的坑：如果 n 刚好等于链表长度，first 会从最后一个结点走到 NULL，但这时候不应该视为非法，而应该继续执行删除头结点的逻辑。所以判断非法 n 的时机要在“first 走完 n 步之后”，如果 first 为 NULL 但 n 等于链表长度，有些实现会因为 while 循环条件first->next != NULL直接访问空指针，导致崩溃。解决方法是：要么先判断 first 是否为 NULL 再访问 next，要么统一用first != NULL作为终止条件并采用走 n+1 步的写法。

在实际刷题时，我更推荐保证 n 合法的前提下专注核心算法，代码里可以适当加一行注释说明 n 的约束。但如果是在真实项目里封装链表工具函数，非法输入处理不能省。

4. 实战中踩过的坑与排查实录

4.1 没加虚拟头结点导致的分支混乱

我第一次自己写这道题的时候，没有用虚拟头结点，结果代码里全是 if。删除头结点时head = head->next，删除尾结点时还要判断second->next->next是否存在，写着写着就把自己绕进去了。

后来我把两种写法放在一起对比，才意识到虚拟头结点不是花哨技巧，而是“把链表当作带哨兵的双端结构来操作”的工程习惯。在很多底层链表实现中，哨兵结点本身就是链表的一部分，它让“空表非空”成为事实，头插尾插删除都不再需要判断 head 是否为空。面试时如果你能主动说出“我加一个虚拟头结点，这样就不用特判删除头结点”，面试官通常会点头，因为这说明你不是在背答案，而是真的踩过这个坑。

4.2 释放结点时指针悬挂

C 语言版本里，删除结点后如果不free，就是内存泄漏；如果先free再访问它的 next，就是悬空指针。

正确顺序是：先用一个临时变量保存被删结点的地址，把前驱的 next 接好后继结点，再释放临时变量。也就是说，顺序是“先改链、后释放”。我在本地调试时曾经把顺序写成先 free 再改指针，结果释放之后再去读toDelete->next，已经不知道那块内存里还剩什么了，程序跑起来时对时错，排查了很久。

如果你写的删除操作后面不需要再用被删结点的数据，一律按这个顺序来。如果被删结点需要在释放前取走数据，那就先保存数据、再改链、再释放。

4.3 面试追问：如果换成循环链表怎么办

这是我在面试中实际追问过别人的问题。把单链表换成循环单链表，问如何删除从某个结点开始数的倒数第 n 个结点。这时候“倒数”这个概念会变得模糊，因为循环链表没有严格的末尾。常见的处理方式是把问题转化为约瑟夫环的计数，或者指定一个起点结点，从它开始数 n 步。这个变体的重点已经不是双指针，而是“如何处理环形结构中的终止条件”，通常需要引入步数计数或者环长度判断。

顺着这个方向，还会引出“如何判断链表有环”“如何找到环的入口”等经典问题。这些问题的核心仍然是快慢指针。所以这道题虽然只是删除一个结点，但它带出来的双指针思想，是可以一路延伸到整个链表题型的地基。

4.4 自查清单：写完后必须检查的用例

我在本地练这道题时，给自己列了一个清单，每次写完代码都会跑一遍：

• 链表 1 -> 2 -> 3 -> 4 -> 5，删除倒数第 2 个结点，结果应为 1 -> 2 -> 3 -> 5；
• 链表 1 -> 2 -> 3，删除倒数第 3 个结点即头结点，结果应为 2 -> 3；
• 链表 1，删除倒数第 1 个结点，结果应为空；
• 链表 1 -> 2，删除倒数第 1 个结点即尾结点，结果应为 1；
• 链表为空时，直接返回空。

前两个用例验证普通情况和头结点情况，第三个验证空结果，第四个验证尾结点，第五个验证空链表。如果你没有用虚拟头结点，建议把这个清单里的第 2、3 条当作重点检查对象。每一次都能一次性通过，这才说明代码写稳了。

5. 从这道题延展出的链表基本功

5.1 链表 vs 数组：为什么删除看起来简单却容易出错

数组删除中间元素需要把后面的元素整体前移，时间复杂度 O(L)，链表删除只是改一个 next 指针，看起来是 O(1)。但链表的前提是“你已经站在被删结点前驱的位置上”。找这个前驱的过程，常常是 O(L)。

这个矛盾点就是这道题设计得巧妙的地方：它没有直接给被删结点，而是给了一个“倒数第 n 个”的位置描述。你要么先遍历一遍求出总长度，要么用双指针把“找前驱”和“找末端”合并到同一个遍历过程里。无论哪种做法，都不可能避开 O(L) 的查找时间。链表真正的优势不在随机访问，而在插入删除时不需要移动大量数据，以及存储空间可以动态分布。用得好的工程实践，比如 Linux 内核链表、LRU 缓存、编辑器的撤销栈，都是建立在这种特性上的。

5.2 围绕这道题的一串变体题

删除倒数第 n 个结点练熟之后，可以顺手把下面这些变体也过一遍，它们会反复用到刚才的思想：

• 找链表中间结点：快慢指针，fast 每次走两步，slow 每次走一步，fast 走到尾时 slow 就是中间点；
• 判断链表是否有环：同样的快慢指针，如果相遇说明有环；
• 合并两个有序单链表：可以用一个虚拟头结点作为新链表的起点，不断比较两个链表头结点的大小；
• 单链表反转：虽然不是双指针，但同样是在链表指针操作上做文章，适合作为下一道练手题；
• 基于链表实现集合差集：需要遍历、比较、删除，核心同样是结点前驱的管理。

如果你用的是 PHP、Go、Java 这些语言，逻辑完全一样，只是语法不同。比如 PHP 里没有指针语法，但对象的引用语义天然符合链表结点的连接方式；Go 的结构体指针操作和 C 很像，只是没有手动free，依赖垃圾回收。基于同样的算法思路，换语言最多只是半小时的事。

5.3 链表在实际项目中的地位

很多写业务代码的人可能一年都碰不到一次“手动处理链表结点”，但底层框架里链表无处不在：内存池的空闲块管理、操作系统的进程队列、浏览器历史记录、JSON 解析中的嵌套结构，都能看到链表或者类链表的思想。

我记得有一次在公司排查内存占用问题时，就遇到过一段用链表维护缓存节点的代码。当时删除缓存项的接口有一个 bug：删掉第一个缓存节点后，链表的头指针没有更新，导致后续查询全部命不中缓存，数据源被反复打到慢查询上。那个问题的修复方式和这道题一模一样：加一个虚拟头结点，统一删除逻辑。所以不要觉得刷题离工作远，有时候你遇到的生产事故，本质就是一道边缘条件拿捏不准的链表题。

最后分享一个我自己用了很多年的习惯：写链表题之前，先在纸上画出结点和指针的位置，标好 first 和 second 的起点，模拟三步走，然后再动键盘。这个习惯帮我避开了绝大部分空指针问题。这道题的完整价值在于，它把“找前驱”、“处理头结点”、“一次遍历”这些链表核心思想全部串了一遍，你把它吃透，后面再看到反转链表、合并链表、成环判断，都会觉得它们像是同一个知识树上的分支，而不是一道道孤立的新题。