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

题目

力扣题目

给定单链表头节点 head，删除链表的倒数第 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]

提示：

• 链表节点数为 sz，1 <= sz <= 30
• 1 <= n <= sz

考察内容

• 快慢指针固定间距
• 倒数位置与正向遍历的转换
• 使用虚拟头节点删除原头节点
• 前驱节点定位
• 节点释放

解题思路

快慢指针

创建虚拟头节点 dummy 并让它指向 head。令 fast 和 slow 都从 dummy 出发：

1. 先让 fast 向前移动 n 步；
2. 再让两个指针同步移动，直到 fast 位于最后一个节点；
3. 此时 slow->next 恰好是倒数第 n 个节点；
4. 绕过并删除 slow->next。

为什么 slow 最终停在待删除节点的前驱？两个指针始终相隔 n 条边。当 fast 到达最后一个节点时，slow 到链表末尾还相隔 n 条边，所以 slow->next 正是倒数第 n 个节点。

使用虚拟头节点后，即使删除的是原头节点，slow 仍可停在 dummy 上，通过同一套逻辑完成删除。

以 [1,2,3,4,5]、n=2 为例：

• fast 先从 dummy 移动到节点 2；
• 快慢指针同步前进；
• fast 到达节点 5 时，slow 位于节点 3；
• 删除 slow->next，即节点 4。

• 时间复杂度：$O(L)$，L 为链表长度
• 空间复杂度：$O(1)$

两趟扫描

也可以先统计链表长度 L，再从虚拟头节点移动 L-n 步找到前驱。思路简单，但需要遍历两次；快慢指针把两趟合并为一趟。

代码演示

struct ListNode {
    int val;
    ListNode* next;

    explicit ListNode(int value = 0, ListNode* nextNode = nullptr)
        : val(value), next(nextNode) {}
};

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

    // fast 先走 n 步，使 fast 与 slow 相隔 n 条边
    for (int i = 0; i < n; ++i) {
        fast = fast->next;
    }

    // fast 到达尾节点时，slow 位于待删除节点的前驱
    while (fast->next != nullptr) {
        fast = fast->next;
        slow = slow->next;
    }

    ListNode* deleted = slow->next;
    slow->next = deleted->next;
    delete deleted;

    return dummy.next;
}

易错点

• 快指针步数与循环条件不匹配：若先走 n 步，应使用 while (fast->next)；若先走 n+1 步，则应使用 while (fast)，不能混用。
• 让 slow 停在待删除节点上：删除单链表节点通常需要它的前驱，因此这里从 dummy 出发保持间距。
• 没有使用虚拟头节点：删除倒数第 L 个节点就是删除头节点，容易产生额外分支。
• 宽度理解错误：两个指针相隔的是 n 条 next 边，不是中间有 n 个节点。
• 删除后继续访问旧节点：先重连，再释放，之后不能访问 deleted。
• 忘记返回新头节点：应返回 dummy.next，原 head 可能已经被删除。

总结

倒数第 n 个位置可以通过固定间距的快慢指针定位。虚拟头节点让 slow 始终能落在目标前驱位置，从而统一处理中间节点与头节点删除。

相关题目

• 206. 反转链表
• 141. 环形链表
• 203. 移除链表元素
• 876. 链表的中间结点