我来给你讲解 LeetCode 第 19 题「删除链表的倒数第 N 个结点」。

1. 题目描述

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

示例 1：
链表：1 → 2 → 3 → 4 → 5，n = 2
删除倒数第 2 个结点（值为 4 的结点）
结果：1 → 2 → 3 → 5

示例 2：
链表：1 → 2，n = 2
删除倒数第 2 个结点（值为 1 的结点）
结果：2

示例 3：
链表：1，n = 1
删除后：返回空链表

要求：

• 一趟扫描实现

2. 思路分析

2.1 直观思路

要删除倒数第 N 个结点，我们需要知道它的前一个结点，然后让前一个结点指向倒数第 N 个结点的下一个结点。

关键问题： 如何一次遍历找到倒数第 N 个结点？

2.2 双指针技巧（快慢指针）

我们可以使用两个指针：

• 快指针 fast 先走 N 步
• 慢指针 slow 从链表头开始
• 然后两个指针同时移动，直到快指针到达链表末尾
• 此时慢指针指向的就是倒数第 N 个结点的前一个结点

为什么？
因为当快指针走了 N 步后，快慢指针之间相隔 N 个结点。当快指针到达末尾（null）时，慢指针正好在倒数第 N 个结点的前一个位置。

3. 详细步骤

3.1 处理边界情况

如果要删除的是头结点（即 N 等于链表长度），我们需要特殊处理。
使用虚拟头结点（dummy node）可以简化操作。

3.2 具体步骤

1. 创建虚拟头结点 dummy，其 next 指向真正的头结点
2. 初始化快慢指针都指向 dummy
3. 快指针先向前移动 N 步
4. 然后快慢指针同时移动，直到快指针到达链表末尾
5. 此时慢指针的 next 就是要删除的结点
6. 执行删除操作：slow.next = slow.next.next
7. 返回 dummy.next

4. 举例说明

以链表 1 → 2 → 3 → 4 → 5，n = 2 为例：

步骤 1： 创建虚拟头结点，指向 1
dummy → 1 → 2 → 3 → 4 → 5

步骤 2： 快慢指针都指向 dummy

步骤 3： 快指针先走 2 步：
fast 指向 2（值为 2 的结点）
slow 指向 dummy

步骤 4： 同时移动快慢指针：

• fast 指向 3，slow 指向 1
• fast 指向 4，slow 指向 2
• fast 指向 5，slow 指向 3

步骤 5： 此时 slow 指向 3（倒数第 2 个结点的前一个）
slow.next 指向 4（要删除的结点）

步骤 6： 执行删除：3 → 5

结果： 1 → 2 → 3 → 5

5. 代码实现

def removeNthFromEnd(head, n):
    # 创建虚拟头结点，处理删除头结点的特殊情况
    dummy = ListNode(0)
    dummy.next = head
    
    slow = fast = dummy
    
    # 快指针先走 n 步
    for _ in range(n):
        fast = fast.next
    
    # 同时移动快慢指针，直到快指针到达末尾
    while fast.next:
        slow = slow.next
        fast = fast.next
    
    # 删除倒数第 n 个结点
    slow.next = slow.next.next
    
    return dummy.next

6. 复杂度分析

• 时间复杂度： O(L)，其中 L 是链表长度，只需要一次遍历
• 空间复杂度： O(1)，只使用了常数级别的额外空间

7. 关键点总结

1. 虚拟头结点 简化了删除头结点的特殊情况处理
2. 快指针先走 N 步 建立两个指针之间的固定间隔
3. 同时移动 直到快指针到达末尾，慢指针自然指向目标位置
4. 要删除的是 slow.next，不是 slow

这个解法巧妙地将"倒数第 N 个"转化为"正数第 L-N+1 个"的问题，通过双指针的一次遍历高效解决。