LeetCode LCR 021. 删除链表的倒数第 N 个结点
题目描述
题意分析
删除单链表从末尾数起的第
n个节点，返回删除后的头节点。倒数第一是尾节点，n等于链表长度时删除头节点；单节点链表删除后应返回空。题目保证链表非空且
n在有效范围内。单链表删除一个节点需要改动它前驱的next，所以定位目标时最好同时找到前驱。进阶要求一趟扫描完成，不能依赖先遍历求出总长度、再重新定位。
解法：快慢指针保持固定间隔
核心思路
[!blue]
如果让两个指针保持固定距离，前面的指针到达尾部时，后面的指针就能据此知道自己的倒数位置。由于真正要找的是待删节点的前驱，目标距离应当是：前驱沿
next走n步到达尾节点。在原头节点之前加上哑节点
dummy，fast与slow都从它出发。先让fast独自前进输入所要求的n步，此时从slow走同样步数正好到达fast。接着两个指针每轮各走一步，间距保持不变。同步移动在
fast.next为空时停止，也就是让快指针停在真实尾节点，而不是尾后的空位置。此时慢指针到尾部恰好有n条边，因此它的下一节点到尾部有n - 1条边，正是倒数第n个节点。把slow.next改成slow.next.next即完成删除。哑节点解决的是头节点没有真实前驱的边界。若
n等于链表长度，快指针在初始前进后已经到尾部，慢指针仍停在dummy，直接改动dummy.next就能删头。单节点情形同样会把它改为空；因此最后必须返回dummy.next，而不是可能已经被删除的原head。这组初始化、领先步数和停止条件需要一起理解：当前实现是从哑节点出发、领先
n步、停在尾节点。改变其中某一项就要重新推导慢指针落点，不能混用其他写法的间隔。
解题步骤
- 创建指向原头节点的
dummy，两个指针都从哑节点开始。- 让
fast单独沿链表前进n步，建立固定间隔。- 只要
fast.next非空，就让fast、slow同时前进一步。- 快指针到尾部后，慢指针停在待删节点前驱，执行
slow.next = slow.next.next。- 返回
dummy.next，统一覆盖删头、删尾和删唯一节点。
代码实现
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 哑结点让「删头」与「删中间」走同一条路径。
ListNode dummy = new ListNode(0, head);
ListNode fast = dummy;
ListNode slow = dummy;
while (n-- > 0) {
fast = fast.next;
}
// 停在尾节点时，slow 距尾 n 步，即待删节点的前驱。
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
// 哑结点让「删头」与「删中间」走同一条路径。
dummy := &ListNode{0, head}
fast := dummy
slow := dummy
for n > 0 {
fast = fast.Next
n -= 1
}
// 停在尾节点时，slow 距尾 n 步，即待删节点的前驱。
for fast.Next != nil {
slow = slow.Next
fast = fast.Next
}
slow.Next = slow.Next.Next
return dummy.Next
}
复杂度分析
- 时间复杂度：
O(L)，其中L是链表长度。快指针单向走到尾部，慢指针也只单向前进，无需重新从头开始扫描。- 空间复杂度：
O(1)。只增加一个哑节点和两个移动指针。
关键点总结
[!green]
- 删除需要找到前驱，固定间隔应围绕前驱到尾部的距离设计。
- 同速推进保持输入所规定的间隔，尾部位置将相对距离转化为倒数位置。
- 哑节点为原头节点提供统一前驱，不需要为删头额外分支。
- 返回哑节点的后继，才能拿到可能已经改变的新头。
易错点总结
[!yellow]
- 把当前写法的停止条件改成
fast != null：会多推进一步，使慢指针越过所需前驱。- 领先步数与起点混用：必须一起推导初始化位置、固定间隔与停止位置，不能只记住某个数字。
- 只移动
slow变量来删除：局部引用变化不会修改链表，需要改前驱的next。- 最终返回原
head：删头时它已不属于结果，应该返回dummy.next。- 忽略有效
n的前提：当前初始化按题目保证前进，不能把它解释成处理任意越界输入的通用接口。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 2095. 删除链表的中间节点 | 中等 | 同样先定位待删节点前驱，原题删中点，本题利用快慢指针的固定间隔定位倒数第n项。 |
| 203. 移除链表元素 | 简单 | 同样用哑节点统一删除头节点，原题按值可能删多个，本题按位置只删一个。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！