19. 删除倒数第N个结点（Remove Nth Node From End of List）

频次 ★★★★★ · 难度 🟡 · 高频：全厂

题目

给定链表头节点，删除倒数第 n 个节点，返回链表头节点。

示例：

输入: head = 1 -> 2 -> 3 -> 4 -> 5, n = 2
输出: 1 -> 2 -> 3 -> 5

思路

快慢双指针 + 哑节点：快指针先走 n 步，然后快慢指针一起走，快指针到达链表尾（null）时，慢指针恰好停在待删除节点的前一个节点。用哑节点 dummy 统一处理”删除的是头节点”这种边界情况。

代码

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy, slow = dummy;
 
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}

复杂度

• 时间：O(n) — 一次遍历
• 空间：O(1)

边界条件

• n 等于链表长度（删除头节点）：fast 走完 n 步后恰好为 null，while (fast.next != null) 循环不执行，slow 仍指向 dummy，dummy.next = dummy.next.next 正确删除原头节点。
• 链表只有一个节点、n == 1：同上，删除后返回 dummy.next == null。
• 题目保证 n 合法（1 <= n <= 链表长度），不需要处理 n 越界的情况。

变式

• 删除正数第 n 个节点：直接遍历计数，不需要双指针技巧，本题的难点专门在”不知道链表总长度、只给了倒数第几个”这个设定上。
• 只给单向链表却要求 O(1) 额外空间求”倒数第 k 个节点的值”：同样的快慢指针平移技巧，不需要真的算出链表长度。

易错点

• 若不用哑节点，删除头节点（n == 链表长度）需要单独判断；哑节点让这种情况和其他情况走同一套逻辑。
• 快指针要先走 n 步而不是 n - 1 步，否则慢指针会多停一位，删错节点。

面试追问

• 为什么要先让快指针走 n 步再同步移动，而不是先计算链表总长度？ 计算总长度需要遍历一遍链表，再算出正数第几个然后再遍历一遍去删除，是两趟遍历；快慢指针平移的方法只需要一趟遍历，是更优的解法，面试官通常会用”能不能只遍历一次”来引导到这个思路。
• 如果链表长度未知且非常长（比如是一个流式生成的链表，无法提前知道总长度），双指针方法还适用吗？ 适用，双指针方法本身就不需要提前知道总长度，这也是它相对于”先数长度再定位”方法的核心优势。

关联题

• 同套路：876. 链表的中间结点 —— 双指针定位：本题用固定间距，它用速度差
• 易混：141. 环形链表I —— 同叫”快慢指针”，但那边是判环不是定位
• 知识点：dummy 结点统一”删的是头结点”的边界，同见 24. 两两交换链表结点