删除链表的倒数第 N 个结点
Remove Nth Node From End of List
删除链表倒数第 n 个节点并返回头节点，一趟扫描完成。
在力扣中练习题目描述
给你一个链表，删除链表的倒数第 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 <= 300 <= Node.val <= 1001 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
解题思路
快慢指针 · 一趟扫描
两人隔开 n+1 步，fast 到底时 slow 正好停在待删节点的前驱
先数长度再删除需要走两遍。快慢指针通过固定间隔，把“倒数第 n 个”转成“fast 走到空时，slow 正好停在目标前驱”。
自拟主例 head=[8,3,8,-1,5,2]，n=3，删除 -1，结果 [8,3,8,5,2]。两个 8 是不同节点，图中用稳定的位置编号区分。
fast 和 slow 都从哑节点出发；需要让 fast 先走 n+1 步。
两指针从哑节点出发，fast 先走 n+1 步，再一起移动。这里多走的一步是为了让 slow 停在前驱，而不是待删节点本身。
先行第 4/4 步，fast=-1。
保存 victim=slow->next，让前驱指向 victim 的后继，再释放 victim。返回 dummy.next，不能仍返回旧 head；哑节点让删除头节点也走同一套逻辑。只改变一条引用，其余节点身份与相对顺序保持不变。
易错点
- fast 只走 n 步：slow 会停在待删节点本身，拿不到前驱，删不掉。
- 删完返回 head：如果删的正是头节点，head 已经不在链表里了。
- 把同步前进写成先移 slow 再判断 fast，会多走一步，删错节点。
两次遍历 · 数长度
先数出总长 L，再走 L−n 步找前驱
正确的两次遍历，先数长度再找前驱；思路直观，主解法则用固定间隔只走一遍。
最朴素的思路，先确认它为什么也对：
- 第一趟
for (ListNode* p = head; p; p = p->next) ++len得到总长度 L； - 要删的是正数第
L - n + 1个，它的前驱是正数第L - n个； - 从 dummy 出发走
L - n步，就停在那个前驱上，改一次next即可。
这里仍然保留 dummy，原因和一趟版一样：L - n == 0（要删头节点）时前驱就是 dummy，代码不需要分支。
两趟扫描的时间也是 O(n)，只是常数大一点；空间同为 O(1)。面试时如果一趟版写不顺，两趟版至少保证正确，再往一趟优化。
- 1第一趟遍历，数出链表长度 len。
- 2建 dummy，从 dummy 出发走 len - n 步。
- 3prev->next = prev->next->next，跳过目标节点。
- 4返回 dummy.next。
易错点
- 把 len - n 写成 len - n + 1，会停在待删节点上，删掉的是它的后继。
- 忘了 dummy，删头节点时 prev 为空，直接崩溃。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
head = [8,3,8,-1,5,2], n = 3fast 和 slow 都从哑节点出发；需要让 fast 先走 n+1 步。
查看 C++ 代码
延伸阅读
- 快慢指针的「间距」就是倒数序号的度量衡：这类题的关键是让间距等于 k，而不是背具体步数。
- dummy 哨兵在链表题里几乎万能：删除、插入、合并、拆分都可以先加一个假头，省掉边界特判。
- 同源题：环形链表（141）用快慢指针判相遇，环形链表 II（142）再加一次从头同步走来定位入口。