Q19 删除链表的倒数第N个节点

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

我的想法 自己独立做出来了。过程中解决了两个疑问：

• fast 先走会不会越界？模拟后确认不会——fast 恰好走到 nullptr 这个合法终点就停。
• 删除后 return 不好 return？因为头可能被删，答案必须从 dummy->next 拿；而且顺序是：先重接、再删除；先读答案、再删 dummy。

这篇笔记的核心 虚拟头 + 快慢指针：fast 先走 n+1 步，再快慢一起走，slow 正好停在"目标节点的前驱"。删除顺序：先重接，再删除；先读答案，再删 dummy。

1 简要回答

1. fast 从 dummy 出发先走 n+1 步。
2. fast、slow 一起走，直到 fast == nullptr。此时 slow 是倒数第 n 个节点的前驱。
3. 重接链表、删除目标节点，返回 dummy->next。

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$。

2 详细回答

2.1 为什么 fast 先走 n+1 步不会越界

假设链表长度是 L，n 最大等于 L。从 dummy 出发走 n+1 步，最多走 L+1 步：

1

dummy(0) → 1(1) → 2(2) → … → nodeL(L) → nullptr(L+1)

最后一步是在 nodeL 上执行 fast = fast->next，结果是 nullptr——nullptr 是合法终点，不是越界。真正的越界只发生在对 nullptr 解引用时（比如 fast 已经是 nullptr 还写 fast->next）。只要步数设计成"恰好停在 nullptr"，并且后续循环先检查 fast != nullptr，就不会崩。

2.2 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(0, head);
    ListNode* fast = dummy;
    ListNode* slow = dummy;

    for (int i = 0; i <= n; ++i) {   // fast 先走 n+1 步
        fast = fast->next;
    }
    while (fast != nullptr) {        // 快慢一起走
        fast = fast->next;
        slow = slow->next;
    }
    // 现在 slow 是目标节点的前驱
    ListNode* target = slow->next;   // ① 记住要删的节点
    slow->next = slow->next->next;   // ② 先重接链表（摘下来）
    delete target;                   // ③ 再删除目标

    ListNode* result = dummy->next;  // ④ 先读答案
    delete dummy;                    // ⑤ 再删 dummy（可选）
    return result;
}

2.3 我的实现（验证通过）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummyhead = new ListNode(-1, head);
    ListNode* fast = dummyhead;
    ListNode* slow = dummyhead;
    fast = fast->next;                 // 先手动走 1 步
    for (int i = 0; i < n; i++) {      // 再走 n 步，合计 n+1 步
        fast = fast->next;
    }
    while (fast != nullptr) {
        fast = fast->next;
        slow = slow->next;
    }
    auto temp = slow->next;
    slow->next = slow->next->next;
    delete temp;
    return dummyhead->next;
}

• 和标准写法等价：手动 fast = fast->next + for 循环 n 步 = 从 dummy 一共走 n+1 步。
• 没 delete dummyhead 也没关系（LeetCode 不检查泄漏）；如果要删，先 result = dummyhead->next 再删。

2.4 删除与返回的顺序（我卡过的地方）

• 先重接，再删除：必须先把 slow->next 指向目标的下一个，目标才能从链表里摘下来；先 delete target 的话，链表还挂着指向已释放内存的指针 → use-after-free（之前见过的 ASan 报错）。
• 先读答案，再删 dummy：result = dummy->next 必须在 delete dummy 之前；顺序反了就是读已释放内存。不删 dummy 也不会错（LeetCode 不检查泄漏），删了是好习惯。
• 为什么答案从 dummy->next 拿：当 n == 链表长度时，删除的是原头节点，head 指向的节点已经没了；而 dummy->next 在重接时自动更新成新头，所以它永远是"当前真实头"。

3 知识扩展

易错点

• 删除目标节点前，必须先重接链表。
• n 等于链表长度时，删的是头：此时 slow 就是 dummy，dummy->next 自动变成原第二个节点。
• 先走 n 步还是 n+1 步，取决于循环条件：n+1 步 + while (fast) 和 n 步 + while (fast->next) 等价，选一种记熟。
• 空链表（head 为 null）时循环条件要能安全退出。

3.1 相关笔记

• Q206 反转链表（dummy 的用法）
• Q24 两两交换链表中的节点（先重接再删除/交换）
• 空指针与虚拟头节点（dummy 站岗，dummy->next 交卷）
• 指针交接瞬间（改指针前先防断链）
• 链表常用操作总结

3.2 自测

• 能解释 fast 先走 n+1 步为什么不会越界
• 能说出删除三步的顺序：记住目标 → 重接 → 删除
• 能解释为什么答案必须从 dummy->next 拿
• 能说出 n == 链表长度时，slow 停在哪里
• 手写一遍完整代码