🔗 删除链表的倒数第 N 个结点

题目来源：19. 删除链表的倒数第 N 个结点 – 力扣（LeetCode）

📌 题目描述

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

• 链表结点数 sz 满足 1 <= sz <= 30
• 1 <= n <= sz（保证 n 有效，不会越界）
• 结点值范围：0 <= Node.val <= 100

✅ 示例解析

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
解释：倒数第 2 个结点是值为 4 的结点，删除后链表变为 1→2→3→5。

示例 2：

输入：head = [1], n = 1
输出：[]
解释：链表只有一个结点，删除后为空。

示例 3：

输入：head = [1,2], n = 1
输出：[1]
解释：删除倒数第 1 个（即最后一个）结点 2。

⚠️ 提示

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

💡 解法：快慢指针 + 虚拟头节点 —— O(n) 时间，O(1) 空间

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        
        // 第一步：fast 先走 n 步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        
        // 第二步：fast 和 slow 同时前进，直到 fast 到达最后一个节点
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        // 第三步：删除 slow.next（即倒数第 n 个节点）
        slow.next = slow.next.next;
        
        // 第四步：返回真实头节点
        return dummy.next;
    }
}

📊 复杂度分析

• 时间复杂度：O(n)
  • 快指针先走 n 步，再与慢指针同步走到尾，总共不超过 2n 步 → 线性时间。
• 空间复杂度：O(1) ✅
  • 仅使用常数个指针（dummy, fast, slow），无递归、无额外数组。

🧩 解题思路

核心思想：双指针（快慢指针）定位倒数第 n 个节点的前驱节点

1. 为什么用虚拟头节点？
   • 避免删除头节点时的特殊处理（如示例2：[1], n=1）。
   • 统一所有删除操作：总是删除 slow.next。
2. 快慢指针原理：
   • fast 先走 n 步 → 此时 fast 与 slow 相距 n 个节点。
   • 然后 fast 和 slow 同时前进，直到 fast.next == null（即 fast 到达尾节点）。
   • 此时 slow 恰好停在倒数第 n 个节点的前一个节点。
   • 执行 slow.next = slow.next.next 即可删除目标节点。
3. 举例说明：

输入：head = [1,2,3,4,5], n = 2

初始：
dummy → 1 → 2 → 3 → 4 → 5
slow^   fast^（先走2步后）

第1步：fast 走2步 → 停在 2
dummy → 1 → 2 → 3 → 4 → 5
slow^       fast^

第2步：fast 和 slow 同步前进，直到 fast.next == null
dummy → 1 → 2 → 3 → 4 → 5
            slow^     fast^

此时 slow.next 是 4（倒数第2个），执行 slow.next = slow.next.next
→ 3 → 5，跳过 4

结果：dummy.next → 1→2→3→5 ✅

边界处理：

• 删除头节点（n = sz）→ fast 走 n 步后，slow 仍在 dummy，slow.next = head，删除后返回 dummy.next。
• 删除尾节点（n = 1）→ fast 走1步后与 slow 同步前进，最终 slow 停在倒数第二个节点，删除最后一个。
• 单节点链表 → fast 走1步到唯一节点，while 不执行，slow 在 dummy，删除 slow.next → 返回 null。