删除倒数第 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，不会越界。