力扣热题100实战 | 第19期：删除链表的倒数第 N 个结点——快慢指针的经典配合

有时候，你不需要知道终点还有多远，只需要找到一个可靠的参照物，就能精准定位目标。快慢指针，就是链表世界里的那个“参照物”。

前言

你好，我是@礼拜天没时间。

上一期我们攻克了四数之和，继续深化了双指针在数组中的应用。这一期，我们切换回链表专题，来解一道非常经典的链表操作题——删除链表的倒数第 N 个结点（LeetCode 第19题）。

这道题在力扣上被标记为“中等”，但它的核心思想并不复杂。然而，越简单的题目越能考察出代码的严谨性——尤其是边界条件的处理。很多同学第一次写这道题时，要么忘了处理删除头结点的情况，要么指针移动的步数算错，导致空指针异常。

今天，我希望能带你从最朴素的思路出发，一步步推导出最优雅的解法，并彻底理解快慢指针的妙用。

一、题目：看不见的“倒数第N个”

先看题目描述（LeetCode 第19题）：

给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 解释：删除倒数第二个节点（值为4），得到 [1,2,3,5]

示例 2：

输入：head = [1], n = 1 输出：[] 解释：删除唯一的一个节点，链表变为空

示例 3：

输入：head = [1,2], n = 1 输出：[1] 解释：删除倒数第一个节点（值为2），得到 [1]

关键点解读

1. 链表的单向性：链表只能从头到尾遍历，无法直接访问倒数第 N 个节点，这是问题的根本难点 。

2. n 的有效性：题目保证1 <= n <= sz（链表长度），所以我们不需要考虑 n 超出范围的情况。

3. 进阶挑战：题目特别要求“你能尝试使用一趟扫描实现吗？”。这意味着我们只能遍历链表一次。

4. 头结点的特殊性：如果要删除的是头结点，操作方式与删除中间节点不同，需要特殊处理 。

二、第一反应：两遍扫描法（直观但不够优）

当我第一次看到这道题，我的第一反应是：先遍历一遍链表，计算出总长度，然后根据总长度和 n 找到要删除节点的前一个节点。

核心思想

1. 第一次遍历，统计链表节点个数len
2. 计算要删除的节点是正数第几个：pos = len - n + 1
3. 第二次遍历，找到第pos - 1个节点（即待删节点的前驱）
4. 执行删除操作pre.next = pre.next.next

代码实现

classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){// 1. 第一次遍历，统计链表长度ListNodep=head;intlen=0;while(p!=null){len++;p=p.next;}// 2. 计算待删节点的正数位置intpos=len-n+1;// 3. 如果要删除的是头结点if(pos==1){returnhead.next;}// 4. 第二次遍历，找到待删节点的前一个节点ListNodepre=head;for(inti=1;i<pos-1;i++){pre=pre.next;}// 5. 删除节点pre.next=pre.next.next;returnhead;}}

复杂度分析

• 时间复杂度：O(L) —— 需要遍历两次链表，总操作次数约 2L
• 空间复杂度：O(1) —— 只用了常数变量

这段代码的优点和问题

✅优点：

• 思路直观，容易理解
• 逻辑清晰，适合初学者

❌问题：

1. 不符合进阶要求：题目希望用一趟扫描实现
2. 效率略低：虽然时间复杂度也是 O(L)，但常数因子是 2
3. 边界处理略显繁琐：需要单独判断删除头结点的情况

三、核心解法：快慢指针法（一趟扫描）

思想来源

如何在一趟扫描中定位到倒数第 N 个节点？答案是利用快慢指针。

想象一下：如果两个人同时从起点出发，一个人先走 N 步，然后两人以相同速度前进。当先走的人到达终点时，后走的人恰好离终点还有 N 步——也就是倒数第 N 个位置。

这就是快慢指针的精髓：利用两个指针的固定间距来定位倒数位置。

算法步骤

1. 初始化两个指针：fast和slow都指向头结点
2. 快指针先走 n 步：让fast领先slow恰好 n 个节点
3. 同时移动两个指针：当fast不为空时，两个指针一起前进，保持间距
4. 定位到目标：当fast到达链表末尾（fast == null）时，slow指向的就是倒数第 n 个节点
5. 删除节点：但我们真正需要的是待删节点的前一个节点，所以需要调整

关键调整：如何得到前驱节点？

上面的思路中，当fast到达末尾时，slow指向的是要删除的节点本身。但我们删除节点需要它的前驱。

解决办法有两种 ：

方案A：让fast先走 n+1 步，这样当fast到达末尾时，slow指向的就是待删节点的前驱。

方案B：让fast先走 n 步，然后当fast.next != null时再同时移动，这样循环结束时slow指向的是待删节点的前驱。

我们采用更优雅的方案A，并结合虚拟头节点简化边界处理。

图解流程

以head = [1,2,3,4,5],n = 2为例 ：

第一步：添加虚拟头节点

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null ^ slow/fast（初始位置）

第二步：快指针先走 n+1=3 步

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null ^ ^ slow fast（走了3步后）

第三步：快慢指针同时移动，直到 fast 为 null

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null ^ ^ slow fast（到达末尾）

此时slow指向节点 3，正是待删节点 4 的前驱。

第四步：执行删除slow.next = slow.next.next

最终结果：[1,2,3,5]✅

四、代码实现：快慢指针 + 虚拟头节点（面试标准答案）

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){// 1. 创建虚拟头节点，简化边界处理ListNodedummy=newListNode(0);dummy.next=head;// 2. 初始化快慢指针，都指向虚拟头节点ListNodefast=dummy;ListNodeslow=dummy;// 3. 快指针先走 n+1 步for(inti=0;i<n+1;i++){fast=fast.next;}// 4. 快慢指针同时移动，直到 fast 为 nullwhile(fast!=null){fast=fast.next;slow=slow.next;}// 5. 此时 slow 指向待删节点的前驱，执行删除slow.next=slow.next.next;// 6. 返回真正的头节点returndummy.next;}}

代码解析

1. 虚拟头节点：dummy节点的引入让代码优雅了很多 ：

   • 避免了对删除头结点的特殊判断
   • 保证了删除逻辑的统一性
   • 即使删除原头结点，dummy.next也能正确指向新头

2. n+1 步的设计：快指针多走一步，是为了让慢指针最终指向待删节点的前驱，而不是节点本身 。

3. 循环条件：while (fast != null)保证了当快指针到达链表末尾时循环结束，此时慢指针恰好就位。

4. 删除操作：slow.next = slow.next.next是标准的链表节点删除操作。

复杂度分析

• 时间复杂度：O(L) —— 只需一趟扫描，每个节点访问一次
• 空间复杂度：O(1) —— 只用了常数变量

五、细节剖析：面试官真正关心的问题

Q1：为什么快指针要提前走 n+1 步，而不是 n 步？

答案：这是为了找到待删节点的前一个节点。

• 如果快指针走 n 步，当它到达末尾时，慢指针指向的是待删节点本身
• 但删除节点需要操作它的前驱，所以我们希望慢指针指向待删节点的前一个
• 多走一步，正好让慢指针落在正确位置

Q2：虚拟头节点在这里起到了什么作用？

答案：虚拟头节点主要有两个作用 ：

1. 统一逻辑：如果没有虚拟头节点，当删除原头节点时，需要单独处理head = head.next。有了 dummy，所有删除操作都可以统一用slow.next = slow.next.next处理。

2. 避免空指针：当链表只有一个节点且要删除它时，没有 dummy 的情况下，慢指针初始指向 head，操作时容易出现空指针异常。

Q3：如果 n 等于链表长度（删除头节点），代码能正常工作吗？

答案：能。让我们验证一下：

• 链表长度 = L，n = L
• 快指针从 dummy 出发，走 n+1 = L+1 步，正好到达 null
• 此时慢指针还在 dummy 处（待删节点 head 的前驱）
• slow.next = slow.next.next等价于dummy.next = dummy.next.next，正好删除了原头节点
• 返回dummy.next即为新的头节点

Q4：循环结束后，fast 和 slow 分别在哪里？

答案：循环结束时：

• fast指向 null（已到达链表末尾）
• slow指向待删节点的前一个节点

这正是我们想要的状态。

Q5：为什么返回值是dummy.next而不是head？

答案：因为原head可能已经被删除了 。使用dummy.next可以确保总是返回正确的头节点，无论删除的是哪个节点。

六、面试官追问进阶版

追问1：如果不允许使用虚拟头节点，代码该怎么写？

思路：需要单独处理删除头节点的情况 。

publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodefast=head;ListNodeslow=head;// 快指针先走 n 步for(inti=0;i<n;i++){fast=fast.next;}// 如果 fast 为 null，说明要删除的是头节点if(fast==null){returnhead.next;}// 同时移动，直到 fast 到达最后一个节点while(fast.next!=null){fast=fast.next;slow=slow.next;}// 删除节点slow.next=slow.next.next;returnhead;}

追问2：如何用栈来实现这道题？

思路：利用栈的“后进先出”特性，可以很容易地找到倒数第 n 个节点。

publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodedummy=newListNode(0);dummy.next=head;Stack<ListNode>stack=newStack<>();// 所有节点入栈ListNodecur=dummy;while(cur!=null){stack.push(cur);cur=cur.next;}// 弹出 n 个节点for(inti=0;i<n;i++){stack.pop();}// 栈顶就是要删节点的前驱ListNodeprev=stack.peek();prev.next=prev.next.next;returndummy.next;}

时间复杂度 O(L)，空间复杂度 O(L)。

追问3：如果要求删除倒数第 n 个节点并返回被删除节点的值，怎么改？

思路：在删除前先保存被删节点的值。

publicintremoveNthFromEndAndReturn(ListNodehead,intn){ListNodedummy=newListNode(0);dummy.next=head;ListNodefast=dummy;ListNodeslow=dummy;for(inti=0;i<n+1;i++){fast=fast.next;}while(fast!=null){fast=fast.next;slow=slow.next;}// 保存被删节点的值intremovedVal=slow.next.val;// 执行删除slow.next=slow.next.next;returnremovedVal;}

追问4：如果链表是双向链表，这道题有什么更简单的解法？

思路：双向链表可以直接从尾节点向前移动 n 步找到目标，不需要快慢指针。但要注意边界处理。

七、实际开发：这道题到底有什么用？

很多读者会问：“删除链表的倒数第 N 个节点，实际工作中哪用得到？”

其实它的思想无处不在：

场景1：滑动窗口限流

在限流算法中，需要维护一个时间窗口内的请求记录。快慢指针的思想可以用来快速定位窗口的边界，淘汰过期的记录。

场景2：TCP 拥塞控制

在 TCP 协议中，发送窗口需要根据网络状况动态调整。快慢指针（或类似的滑动窗口思想）被用来探测网络带宽，避免拥塞。

场景3：版本管理中的回滚

在版本控制系统中，需要回滚到倒数第 N 个版本。快慢指针的思路可以帮助快速定位目标版本，而不需要遍历所有历史记录。

场景4：缓存淘汰策略

在 LRU 缓存中，虽然使用的是双向链表+哈希表，但快慢指针的思想也可以用于某些变种的缓存淘汰算法，如近似 LRU。

场景5：数据流中的滑动统计

在实时数据处理中，需要统计最近 N 个数据点的平均值。维护两个指针可以快速计算滑动窗口内的统计数据。

八、总结：从一道题到一类题

回顾一下，我们从删除链表的倒数第 N 个结点学到了什么：

力扣热题100的第十九题，不是为了难住你，而是为了告诉你：当你在单向的链表里无法回头时，不妨派一个“先锋”先走一步，利用它留下的足迹来定位目标。这种思想，在算法世界里无处不在。

下一期预告：《有效的括号》——栈的经典应用

附录：思考题

看完这篇文章，你可以试着回答：

1. 如果要求删除的是倒数第 n 个节点，但 n 可能大于链表长度，代码需要怎么调整？
2. 如何用递归实现这道题？递归的终止条件和返回值应该是什么？
3. 你能用这道题的思路，去解 LeetCode 876（链表的中间结点）吗？两者都是快慢指针的应用，有什么区别？

欢迎在评论区留下你的思考！