文章目录
LeetCode 19: 删除链表的倒数第 N 个结点
🎯 问题描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
约束条件
- 链表中结点的数目为 sz
- 1 ≤ sz ≤ 30
- 0 ≤ Node.val ≤ 100
- 1 ≤ n ≤ sz
🧠 算法思路分析
方法一：两趟扫描（朴素解法）
思路：
- 第一趟遍历：计算链表长度 L
- 第二趟遍历：找到第 (L-n) 个节点，删除其后继节点
代码示例：
public ListNode removeNthFromEnd(ListNode head, int n) {
// 第一趟：计算长度
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
// 第二趟：找到待删除节点的前驱
ListNode dummy = new ListNode(0);
dummy.next = head;
current = dummy;
for (int i = 0; i < length - n; i++) {
current = current.next;
}
current.next = current.next.next;
return dummy.next;
}
复杂度分析：
- 时间复杂度：O(L)，需要两趟遍历
- 空间复杂度：O(1)
方法二：双指针一趟扫描（最优雅解法） ⭐
核心思想：
使用快慢双指针，快指针先走 n+1 步，然后快慢指针同时移动，当快指针到达末尾时，慢指针正好指向待删除节点的前驱。
算法步骤：
- 创建哑节点：简化边界情况处理
- 快指针先行：快指针比慢指针先走 n+1 步
- 同步移动：快慢指针同时向前移动
- 执行删除：当快指针到达末尾，删除慢指针的下一个节点
🎨 双指针解法详解
可视化演示
以 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
快慢指针同步移动，直到 fast 为 null:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
↑ ↑
slow fast
此时 slow.next 就是倒数第 2 个节点（节点4），删除它:
dummy -> 1 -> 2 -> 3 -----> 5 -> null
↑
slow
关键点解析
1. 为什么使用哑节点？
ListNode dummy = new ListNode(0);
dummy.next = head;
- 统一处理：避免删除头节点时的特殊处理
- 简化逻辑：始终可以通过
slow.next = slow.next.next删除节点
2. 为什么快指针要先走 n+1 步？
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
- 目标：让慢指针指向待删除节点的前驱
- 如果快指针先走 n 步，慢指针会指向待删除节点本身
- 先走 n+1 步，慢指针才能指向前驱节点
3. 删除操作的巧妙之处
slow.next = slow.next.next;
- 直接跳过待删除节点
- 简洁且高效
💻 完整代码实现
/**
* 删除链表的倒数第 n 个结点 - 双指针一趟扫描解法
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
// 创建哑节点，简化边界情况的处理
ListNode dummy=new ListNode(0,head);
// 双指针：fast 和 slow
ListNode slow=dummy;
ListNode fast=dummy.next;
// 快指针先移动 n+1 步
for (int i = 0; i < n; i++) {
fast=fast.next;
}
// 快慢指针同时移动，直到快指针到达末尾
while (fast != null) {
fast=fast.next;
slow=slow.next;
}
// 删除倒数第 n 个节点
slow.next=slow.next.next;
return dummy.next;
}
📊 复杂度分析
时间复杂度：O(L)
- L 是链表的长度
- 只需要一趟遍历，快指针最多移动 L 步
空间复杂度：O(1)
- 只使用了常数个额外指针
- 不依赖于输入规模
🧪 测试用例验证
测试用例 1：常规情况
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
解释：删除倒数第2个节点（值为4的节点）
测试用例 2：删除唯一节点
输入：head = [1], n = 1
输出：[]
解释：删除唯一节点，链表变为空
测试用例 3：删除尾节点
输入：head = [1,2], n = 1
输出：[1]
解释：删除最后一个节点
测试用例 4：删除头节点
输入：head = [1,2], n = 2
输出：[2]
解释：删除第一个节点（倒数第2个）
🎯 算法优势
相比两趟扫描的优势：
- 效率更高：只需一趟遍历
- 空间友好：常数空间复杂度
- 代码简洁：逻辑清晰，易于理解
- 边界处理：哑节点技巧优雅处理特殊情况
双指针技巧的通用性：
- 链表倒数第k个节点
- 链表中点查找
- 环形链表检测
- 链表相交检测
🔧 实现细节和注意点
1. 边界情况处理
// 使用哑节点统一处理删除头节点的情况
ListNode dummy = new ListNode(0);
dummy.next = head;
2. 指针移动的精确控制
// 精确控制快指针的初始位置
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
3. 安全的节点删除
// 确保 slow 指向待删除节点的前驱
slow.next = slow.next.next;
📈 扩展思考
变种题目：
- 删除链表正数第n个节点：直接遍历即可
- 删除链表倒数第k个到第1个节点：双指针+多次删除
- 找到倒数第n个节点但不删除：双指针找到即可
相关算法模式：
- 快慢指针：解决链表相关问题的经典技巧
- 哑节点：简化链表操作的常用手法
- 一趟遍历：提高算法效率的重要思想
🎉 总结
这道题展示了双指针技巧在链表问题中的强大威力。通过巧妙地控制两个指针的相对位置，我们能够在一趟遍历中解决原本需要两趟遍历的问题。这种思想在很多链表算法中都有应用，是非常值得掌握的经典技巧。
关键要点：
- 🎯 双指针一趟扫描是最优雅的解法
- 🛡️ 哑节点简化边界情况处理
- ⚡ 时间复杂度 O(L)，空间复杂度 O(1)
- 🧩 快指针先走 n+1 步是关键
- 🎨 算法思想可推广到其他链表问题