我们来学习 LeetCode 第 19 题「删除链表的倒数第 N 个结点」。

1. 题目描述

给你一个链表，删除链表的倒数第 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]

进阶要求： 尝试使用一趟扫描实现。

2. 思路分析

2.1 直观思路

要删除倒数第 n 个结点，我们需要知道它的前一个结点，才能修改指针完成删除。
如果先遍历一次得到链表长度 L，那么倒数第 n 个结点就是正数第 (L - n + 1) 个结点，删除它需要找到第 (L - n) 个结点。
但这样需要两次遍历：第一次求长度，第二次定位删除。

2.2 一次扫描的思路：双指针

使用快慢指针：

1. 初始时，快指针 fast 和慢指针 slow 都指向哑结点（dummy node，哑结点的 next 指向 head，便于处理删除头结点的情况）。
2. 快指针先向前移动 n 步。
3. 然后快慢指针一起移动，直到快指针到达最后一个结点（即 fast.next 为 null）。
   此时慢指针指向倒数第 n 个结点的前一个结点。
4. 修改慢指针的 next 指向，跳过倒数第 n 个结点。

为什么慢指针会指向倒数第 n 个结点的前一个？

• 快指针先走 n 步，快慢指针之间距离固定为 n。
• 当快指针到达尾结点时（即倒数第 1 个结点），慢指针指向倒数第 n+1 个结点（因为快慢指针相差 n 个结点）。
• 而倒数第 n 个结点的前一个结点就是倒数第 n+1 个结点。

3. 详细步骤

假设链表为 1→2→3→4→5，n=2。

1. 创建哑结点 dummy，dummy.next = head。
2. fast 和 slow 初始都指向 dummy。
3. fast 先走 2 步：fast 指向 2（结点值为 2）。
4. 然后 fast 和 slow 一起移动：
   • fast=2, slow=dummy(0)
   • fast=3, slow=1
   • fast=4, slow=2
   • fast=5, slow=3（此时 fast.next 为 null，停止）
5. slow 在结点 3，slow.next 是结点 4（倒数第 2 个），删除它：slow.next = slow.next.next。
6. 返回 dummy.next。

4. 边界情况

• 链表只有一个结点，n=1：删除后返回空链表。
• 删除头结点（n=链表长度）：哑结点可统一处理。
• 保证 n 有效（1 ≤ n ≤ 链表长度）。

5. 代码实现（Java）

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;
    
    // 快指针先走 n 步
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    
    // 快慢指针一起走，直到快指针到达最后一个结点
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // 删除倒数第 n 个结点
    slow.next = slow.next.next;
    
    return dummy.next;
}

6. 复杂度分析

• 时间复杂度：O(L)，L 为链表长度，只需一次遍历。
• 空间复杂度：O(1)，只用了常数空间存放指针。

这样我们就用双指针技巧在一次遍历内完成了删除链表倒数第 N 个结点的操作。