删除倒数第 N 个结点 图解题解

这道题真正在问什么

给单链表的头节点和一个数 n，删掉倒数第 n 个结点后返回头。难点全在「倒数」两个字上：单链表只能从头往后走、不能回头，而且事先不知道总长度——站在任何一个节点上，你都说不清它是倒数第几个。

两遍扫描为什么能做但不够好

最直接的思路是先扫一遍数出链表总长 L，「倒数第 n 个」就换算成「正数第 L-n+1 个」，再从头走到它的前一个节点做删除。完全正确，但要把链表扫两遍。面试的经典追问是：能不能只走一遍？

关键观察是：「倒数第 n」这个信息虽然单个指针拿不到，但可以翻译成一个相对关系——待删结点与链表末尾之间恰好隔着固定的距离。距离是可以用两个指针「保持队形」来维护的：先把两个指针拉开固定间距，再让它们同速前进，前面的到达终点时，后面的位置就被这个间距唯一确定了。

为什么 fast 要先走 n+1 步而不是 n 步

删除链表节点必须拿到它的前驱，因为删除动作是「前驱.next 跳过待删点」。所以我们真正想让 slow 停的位置不是待删结点本身，而是它前面一个。

把间距设为 n+1：fast 走到 null（越过末尾一格）时，slow 距离末尾 n+1 格，正好落在倒数第 n 个结点的前驱上。如果只拉开 n 步，slow 会停在待删结点身上——单链表到了这里已经拿不到前驱，只能用「复制后继值再删后继」之类的别扭补救。多走的那一步，本质是给「删除需要前驱」这个约束预留的。

哑结点是怎么把删头特判消掉的

有一种情况会让「找前驱」失效：n 恰好等于链表长度，待删的就是头结点，而头结点天然没有前驱。在头前面垫一个不存数据的哑结点 dummy，让 fast 和 slow 都从 dummy 出发，头结点就有了统一的前驱，删头和删中间、删尾用同一段代码，最后返回 dummy.next 就是新头。

这也是链表题的通用经验：凡是「可能对头结点做修改」的操作（删除、插入、反转），加个哑结点几乎总能把边界分支压成零。

复杂度与正确性小结

时间 O(L)：fast 从头到尾恰好走一遍链表，slow 走的路程更短，总步数是线性的。空间 O(1)：只有两个指针加一个哑结点。

正确性可以一句话说清：两个指针同速移动时间距永远不变，所以「fast 到 null」与「slow 在倒数第 n+1 个」是同一时刻发生的同一件事，不依赖链表内容，也不需要知道 L 的具体值。题目保证 n 不超过链表长度，所以 fast 先走 n+1 步时最多走到 null，不会越界。

Python

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)   # 哑结点统一删头/删中
    fast = slow = dummy
    for _ in range(n + 1):      # fast 先走 n+1 步
        fast = fast.next
    while fast:                 # 一起走到 fast 出末尾
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next  # 前驱跳过待删点
    return dummy.next

C++

ListNode* removeNthFromEnd(ListNode* head, int n){
    ListNode dummy(0, head);
    ListNode *fast = &dummy, *slow = &dummy;
    for(int i = 0; i < n + 1; i++) fast = fast->next;
    while(fast){ fast = fast->next; slow = slow->next; }
    slow->next = slow->next->next;
    return dummy.next;
}

Java

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