删除链表倒数第n个结点：双指针与虚拟头结点精讲

删除链表的倒数第 n 个结点我第一次见到这个题目是在刷 LeetCode 的时候第 19 题。当时第一反应是“这有什么难的先遍历一遍知道长度再走一遍删掉不就行了”但真动手写的时候边界条件一堆虚拟头结点、快慢指针、空指针判断每一步都可能出问题。这道题适合所有在准备算法面试、或者刚开始学数据结构的人链表这一关迟早要过它。这道题考察的远不只是“会不会写代码”而是你对链表这种数据结构有没有真正的理解——指针怎么动、边界怎么处理、内存怎么释放。很多初学者把链表删除想成数组删除直接赋值覆盖这在链表里是行不通的。顺着这个思路这篇文章会从题目拆解、核心解法、代码实现、常见问题几个角度把这道题彻底讲透。1. 题目拆解删除倒数第n个结点到底在考什么1.1 先别急着写代码把题目定义清楚题目描述很简单给定一个链表删除链表的倒数第 n 个结点并返回链表的头结点。很多人在第一步就踩坑了因为“倒数第 n 个”这个表述本身就暗藏玄机。链表不同于数组。数组通过下标可以随机访问时间复杂度是 O(1)链表是链式存储结构每个结点只知道下一个结点在哪想知道“倒数第 n 个”是谁你得有一个全局的视角。这是这道题第一个隐性考点——你不可能直接“跳”到倒数第 n 个结点必须先想清楚怎么“数”到它。另一个容易忽略的点是题目说的是删除“结点”不是删除“值”。这意味着你要操作的是指针指向关系而不是简单地比较数据。链表删除的本质是“跳过”这个结点让前一个结点的 next 指向被删结点的下一个结点。如果你脑子里还停留在数组的“移除元素后整体前移”的模型写出来的代码会很别扭。还有一个常见误区很多人上来就写“遍历一遍计算链表长度然后长度减 n 加 1 就是正数第几个结点”。这个思路本身没错但它没把边界情况想清楚。倒数第 1 个结点是最后一个结点倒数第 n 个结点正着数就是第 length - n 1 个。如果 n 刚好等于链表长度你要删的是头结点这时候没有“前一个结点”能让它的 next 跳过谁——这就是经典的边界问题。1.2 边界情况最容易翻车的几个场景这道题表面上是基础题但边界情况的坑非常多。我列一下我见过的高频翻车现场链表只有一个结点n 1。删除后链表为空应该返回 null而不是报错。n 等于链表长度也就是删除头结点。没有前驱结点直接返回 head.next 就行。n 大于链表长度。严格来说这不算合法输入但面试时经常会被问“如果 n 不合法怎么办”。删除的是中间结点涉及前驱结点的 next 指针重新指向还要注意被删结点的内存释放。我第一次手写这道题就是在“n 等于链表长度”这里踩坑的。我没有用虚拟头结点直接处理 head 的特殊情况结果 if 判断写得又长又绕最后还漏了一种情况被一个简单的测试用例打回原形。所以这里先给出一个结论也是后面会反复用到的实操心得处理链表删除问题优先考虑虚拟头结点。在真实头结点前面加一个虚拟头结点能统一处理所有删除场景不用再单独讨论“删除的是头结点”这种特殊情况。这个技巧在后续很多链表操作题里都能用属于一通百通的做法。提示虚拟头结点的原理本质是“人为制造一个前驱结点”。因为删除操作必须要找到被删结点的前驱而头结点恰好没有前驱虚拟头结点就把这个缺口补上了。2. 两种经典解法从两次遍历到一次遍历2.1 朴素思路先测长度再走第二次先把最简单的方案讲透。思路分三步遍历链表统计结点总数 length。计算正数位置target length - n这个 target 表示“被删结点的前驱结点需要走多少步才能到”。从虚拟头结点出发走 target 步停在被删结点的前驱位置让前驱的 next 指向被删结点的 next。这里有个细节为什么是 length - n而不是 length - n 1因为我们要找的是前驱结点不是被删结点本身。删除操作的本质是“改变前驱的指向”只要定位到前驱删除就完成了。举个例子链表是 1 - 2 - 3 - 4 - 5length 5n 2。倒数第 2 个结点是 4删除后链表应该是 1 - 2 - 3 - 5。从前驱结点 3 的角度看从虚拟头结点 dummy 出发走 length - n 3 步正好到达结点 3。这意味着 target 是 3也就是从 dummy 走到前驱的步数。如果用正数位置来理解被删结点是链表中的第 4 个结点它的前驱是第 3 个。虚拟头结点算第 0 个结点从第 0 个走到第 3 个正好是 3 步。这个计算过程一定要在纸上画一遍把结点编号对应清楚才不会在自己的代码里搞混。朴素解法的时间复杂度是 O(L)L 是链表长度空间复杂度 O(1)。两次遍历第一次统计长度第二次定位前驱。这个方案胜在直观适合用来理解题目的含义也适合作为面试时“先给一个能跑通的方案”的起点。2.2 双指针进阶一次遍历搞定如果面试题到这里就结束那它就不配作为经典题了。面试官通常会追问一句“能不能只遍历一遍”这就是双指针快慢指针解法登场的时刻。思路非常巧妙既然要找倒数第 n 个结点不如让两个指针之间有“n 个结点的距离”然后同步往后走。当快指针走到链表末尾null时慢指针的位置正好落在倒数第 n 个结点的前驱上。具体分成四步初始化一个虚拟头结点 dummy它的 next 指向 head。再初始化两个指针 first 和 second都指向 dummy。让 first 先走 n 步。然后 first 和 second 同步走直到 first 走到 null。这时 second 指向的正好是倒数第 n 个结点的前驱。执行删除second.next second.next.next。这里的关键是“走 n 步”和“走 n 1 步”的区别。很多教程说 first 先走 n 步然后和 second 一起走也有的说 first 走 n 1 步这样 second 停在被删结点本身而不是前驱。两种写法都能做但“走 n 步second 指向前驱”更直接因为删除操作需要的本来就是前驱。如果想更直观地理解可以找一个生活类比。想象一列火车有 n 节车厢你站在地面上让一列快车和一列慢车同时出发。快车先在前面拉开 n 节车厢的距离然后两车保持这个距离同步行驶。当快车到站null时慢车离终点还差 n 节车厢——它正好停在倒数第 n 节车厢的前面。双指针的“间距 n”就是这个距离。双指针解法的时间复杂度是 O(L)空间复杂度 O(1)但它只需要一次遍历。在面试场景中这个方案是标准答案也是必须掌握的核心解法。建议你先把朴素解法写一遍再用双指针优化这样能明显感受到两种思路的差别。注意双指针同步走的时候判断条件建议用while (first ! null)而不是while (first.next ! null)。两者步数差一写错了结果完全不对。我第一次写的时候就因为贪图“省一次判断”用后者结果删除的结点位置偏了一位。3. 手写代码的完整实操3.1 虚拟头结点为什么需要它在前面我多次提到虚拟头结点这里展开讲一下。虚拟头结点是一个“哨兵结点”它不存储有效数据纯粹是为了让代码逻辑统一。没有虚拟头结点时写删除逻辑会遇到两个分支删除的是头结点head 要更新为 head.next。删除的不是头结点需要找到前驱修改前驱的 next。这两个分支的代码路径完全不同容易漏判。用虚拟头结点后不管删除哪个结点都是“找到前驱修改前驱的 next”统一成一条路径。代码短了逻辑清晰了bug 也少了。从数据结构的角度理解虚拟头结点实际上是在链条最前面人为增加了一个“通用前驱”让每一个真实结点都拥有前驱。这样“删除任意位置的结点”就变成了同一种操作模式代码的可维护性和可读性都提高了。在实际工程代码里“哨兵结点”这个思想也非常常见不只是链表。比如在数组扩容、缓存淘汰策略、消息队列实现里都会有类似的“占位对象”。所以这道题表面上是让你写一个删除函数实际上是在训练你“能否用一个小技巧把复杂的分支逻辑简化成统一路径”的能力。3.2 核心代码实现与逐行讲解我用 C 语言来写一版因为 C 语言最能体现链表操作的指针本质。先定义链表结点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; // 双指针初始都指向 dummy struct ListNode* first dummy; struct ListNode* second dummy; // first 先走 n 步 for (int i 0; i n; i) { first first-next; } // 两个指针同步走直到 first 到达末尾 while (first ! NULL) { first first-next; second second-next; } // 此时 second 指向被删结点的前驱执行删除 struct ListNode* toRemove second-next; second-next toRemove-next; // 释放被删结点的内存 free(toRemove); // 新的头结点是 dummy-next struct ListNode* newHead dummy-next; free(dummy); // 释放虚拟头结点 return newHead; }逐行过一遍几个关键点dummy必须先申请内存让它成为一个真实存在的结点。它只有next有意义val是随便一个值不需要初始化。first走 n 步时如果 n 不合法比如 n 大于链表长度first会提前变成 NULL后面的循环就会出现空指针解引用。实际刷题时题目保证了 n 是合法输入但面试时你可能被追问。安全的做法是在走 n 步时加一个判断发现first NULL就直接返回 NULL 或者向上层报错。second-next toRemove-next这一步是关键。它把被删结点从链表中“摘出去”。让我踩坑的地方就在这里摘出去之后如果不free(toRemove)在 C 语言里就是内存泄漏。面试时不一定被强制要求处理但工程项目里必须做。最后别忘了释放 dummy。虽然不释放也不会立刻出问题但对于长期写 C 的人这个习惯能避免很多潜在的内存问题。还有一个细节很多教程没讲清楚为什么while (first ! null)循环结束后second恰好指向前驱用“间距”来理解最清楚。循环开始前 first 和 second 间距为 n循环结束后 first 指向 NULL相当于走到了链表的“终点之后”。此时 second 距离终点还有 n 个结点也就是说它停在倒数第 n 1 个结点也就是被删结点的前驱。3.3 多语言版本对照同一个逻辑用不同语言实现能帮你更深刻地理解哪些是“算法本身的逻辑”哪些是“语言的语法约束”。Java 版本public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode first dummy; ListNode second dummy; for (int i 0; i n; i) { first first.next; } while (first ! null) { first first.next; second second.next; } second.next second.next.next; return dummy.next; }Java 有自动垃圾回收不需要手动释放结点所以直接second.next second.next.next就把被删结点丢给 GC 处理了。代码比 C 版本少了几行但核心逻辑一模一样。Python 版本def removeNthFromEnd(self, head: ListNode, n: int) - ListNode: dummy ListNode(0) dummy.next head first dummy second dummy for _ in range(n): first first.next while first: first first.next second second.next second.next second.next.next return dummy.nextPython 版本更简洁。这里有一个 Python 特定的点需要留意first和second都是对结点的引用修改second.next会直接修改链表结构而不是修改局部变量。很多 Python 新手会疑惑“我改了 second 里面的东西为什么原链表也变了”本质是因为second是一个引用它指向的是堆上的同一个结点对象。你可能会问为什么代码里都用dummy ListNode(0)或malloc(sizeof(struct ListNode))这种形式而不是直接用head指针因为算法要求“找到被删结点的前驱”而头结点没有前驱。如果直接拿 head 操作你还需要写if (head target)这种分支代码冗长且容易出错。用虚拟头结点后头结点变成了“有一个虚拟前驱的普通结点”所有删除逻辑就完全统一了。这三种语言各有细节差异但核心算法是同一套虚拟头结点加双指针。建议你练习时把三种都写一遍这样才能把“算法逻辑”和“语言特性”彻底分开。等你能熟练地在三种语言之间无缝切换你的基本功就扎实了。4. 常见问题排查与实战心得4.1 写代码时最容易翻车的几个点刷题平台上这道题的提交通过率不算高原因就是细节太多。我把常见 bug 整理成速查表方便你自查错误类型错误现象正确做法未用虚拟头结点删除头结点时返回了空链表或错乱的链表使用 dummy 统一处理删除头结点的场景快指针先走的步数不对删除的结点整体偏移一位明确是走 n 步停在被删结点前驱还是走 n 1 步停在被删结点本身循环判断条件写错同步走时多走了一步或少走了一步统一用while (first ! null)退出时 first 正好是 NULL忘记释放被删结点内存C/C 出现内存泄漏free 或 delete 被摘出的结点没有处理空链表输入 head 为 NULL 时程序崩溃根据题目条件决定是否提前判空返回值写错返回了 dummy 而不是 dummy.next虚拟头结点只是辅助真实头结点要通过 dummy.next 获取这六种错误我基本全踩过一遍。最典型的一次是第一次写的时候我把 dummy 当成真实头结点返回了导致整条链表多出一个值为 0 的结点测试用例直接全红。排查了很久才发现是返回值写错了。这种错误特别容易出现也特别隐蔽因为编译不会报错只有打印链表才能察觉。4.2 面试官常问的几个变体问题这道题在面试中经常作为“引子”面试官会顺着它问各种变体和扩展。我根据自己的面试经验和当面试官的经历列几个高频追问追问一如果要求“只允许扫描一遍”并且“不能修改链表结构”怎么做这就是原题的难度上限双指针解法正好满足。如果面试官再加一句“不能用额外空间”也不用慌双指针本身就是 O(1) 空间没有使用额外数组或哈希表。追问二如果链表是双向链表怎么删除倒数第 n 个结点双向链表天然有前驱指针问题会简单很多。快指针走 n 步后慢指针直接通过 prev 找到前驱即可。但要注意双向链表同样存在头结点的 prev 为 NULL 的情况判断逻辑不能少。这个问题一般是在考察你有没有理解前驱指针的本质作用而不是背模板。追问三如果要删除所有值为 x 的结点呢这个变体其实比原题更基础也更常见。思路仍然是使用虚拟头结点遍历链表时把值为 x 的结点全部摘除。注意不能只删一个摘除后要继续遍历别漏掉连续相同值的场景。这个变体在有些面试中会作为第一道题出现因为它的删除模式更通用。追问四如果不知道链表长度只知道 n 很小能不能用递归可以。递归到链表末尾回溯时计数计数到 n 时删除对应结点。这种方式本质上是“用调用栈模拟从后往前遍历”时间复杂度还是 O(L)但递归深度等于链表长度链表太长会栈溢出。实际工作中不建议这么干但面试时可以作为思路提一句。追问五如果带有循环链表成环这个解法会怎样这个问题相对冷门但能考察你对链表结构的理解。双指针解法在循环链表中会陷入死循环因为 first 永远不会到达 NULL。如果题目允许成环需要先用快慢指针检测环的存在解除环后再做删除。一般面试不会深挖到这个程度但知道这个前提总比不知道好。4.3 关于这道题的一些实操心得最后分享几个我个人的经验。第一个心得链表题的调试方式。单步调试链表题非常痛苦因为指针跳来跳去很难看清。我后来习惯了在关键操作后打印整条链表用一个简单的循环把每个结点的值打出来。这个方法成本最低效果最好。写一个小工具函数printList(head)放在本地刷题时能用很久。第二个心得动笔画图。遇到链表操作永远先画图再写代码。把每个结点画成方块把 next 指针画成箭头然后在图上模拟一遍双指针移动的过程。我见过太多同学盯着代码看半天都想不通 bug 在哪结果一画图就豁然开朗。链表操作本质是“指针变向”的过程图形化模拟一遍比你盲写十遍代码都管用。第三个心得把链表的“删除”想成“跳过”。链表删除不是把结点抹掉而是让前驱的 next 直接指向被删结点的后驱相当于从前驱这里“跳过去”了。在实际编码时这个比喻非常有用你写代码时只要问自己一句“我要让谁跳过去它的前驱是谁”问题就简单了。提示自己去 LeetCode 上把这道题刷透至少做到——不看题解能写出双指针解法的正确代码并且能在两分钟内讲清楚为什么 second 停在前驱而不是被删结点本身。这道题看似基础但它是链表操作的“基本功测试”。链表相关的很多复杂题目——反转链表、合并有序链表、链表排序——本质上都是在这几个基础操作上叠加额外的逻辑。我在刷题过程中最大的感受是把基础和边界条件弄扎实比刷很多奇怪难题有用得多。这道题我反复出现过无数次笔试考它面试问它教新人讲它。认真把它吃透链表的基本功就攒下了。