删除链表的倒数第 N 个结点
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1
示例 2
示例 3
模拟答题者思考
1. 我先写暴力：第一遍遍历数出链表长度 L，第二遍找到正数第 L - n 个节点的前驱并删除——能过，但要扫两遍。
2. 重复在哪里？两遍扫描本质都是在「定位待删节点的前驱」；如果能让两个指针保持固定间距 n，一遍就能同时完成定位。
3. 快指针先走 n 步，再和慢指针同步前进：当 fast 走到最后一个节点时，slow 正好在倒数第 n+1 个节点（即待删节点的前驱）。
4. 边界：若 n 等于链表长度，删的是头节点——没有前驱可改。加 dummy 哨兵后，slow 会停在 dummy，统一用 slow.next = slow.next.next 删除。
5. 循环条件是 while fast.next 而非 while fast：保证 fast 停在最后一个节点，slow 才恰好落在前驱位置。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dummy | ListNode* | 定义：哨兵头节点，dummy.next = head维护：始终位于真实头节点之前，统一处理「删掉头节点」的边界 更新：创建后不再移动，最终返回 dummy.next |
fast | ListNode* | 定义：快指针，先向前走 n 步维护：与 slow 保持「快指针比慢指针超前 n 个节点」的间距更新：先单独走 n 步，再与 slow 同步每次 fast = fast.next |
slow | ListNode* | 定义：慢指针，从 dummy 出发 维护：当 fast 到达链表末尾时，slow 恰好停在「待删节点的前驱」 更新：与 fast 同步每次 slow = slow.next，最后执行 slow.next = slow.next.next |
落码步骤
1. 创建哨兵 dummy = ListNode(0, head)，fast = slow = dummy
2. 快指针先走 n 步：for _ in range(n): fast = fast.next
3. 双指针同步前进：while fast.next: fast = fast.next; slow = slow.next
4. 删除节点：slow.next = slow.next.next
5. 返回 dummy.next（新头节点）
代码实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head) # 哨兵，统一处理删头节点
fast = slow = dummy
for _ in range(n): # 快指针先走 n 步
fast = fast.next
while fast.next: # 同步前进，fast 到末尾时 slow 在前驱
fast = fast.next
slow = slow.next
slow.next = slow.next.next # 跳过待删节点
return dummy.nextclass Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0, head); // 哨兵，统一处理删头节点
ListNode* fast = &dummy;
ListNode* slow = &dummy;
for (int i = 0; i < n; i++) // 快指针先走 n 步
fast = fast->next;
while (fast->next) { // 同步前进，fast 到末尾时 slow 在前驱
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next; // 跳过待删节点
return dummy.next;
}
};
// 时间 O(n)，空间 O(1)
// 两遍法：先数长度 L，再走到第 L-n 个节点的前驱删除复杂度分析
O(n)
O(1)
常见坑
忘记 dummy 哨兵：当 n == 链表长度 时要删头节点，没有前驱可改 next，必须用哨兵统一处理。
循环条件写成 while fast：fast 会走出链表，slow 停在错误位置；应是 while fast.next，让 fast 停在最后一个节点。
快指针少走或多走一步：先走恰好 n 步（不是 n-1 也不是 n+1），间距错了 slow 就对不准前驱。
必测边界 Case
head = [1], n = 1 → []
head = [1,2], n = 1 → [1]
head = [1,2,3,4,5], n = 2 → [1,2,3,5]（删倒数第 2 个即 4）