63.删除链表的倒数第 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 <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
思路
难点在于"倒数"
如果题目说的是"删除正数第 n 个"，那太简单了——从头走 n-1 步就到了。
但这里是倒数第 n 个。链表是单向的，我们没法从尾巴往回走。最朴素的办法是：先遍历一遍数出总长度 L，那么倒数第 n 个就是正数第 L - n + 1 个，再走一遍去删。这需要走两遍。
有没有办法只走一遍就找到倒数第 n 个？有，用快慢双指针。
快慢指针：制造一个"固定的间距"
核心思想非常巧妙：
- 让两个指针 fast 和 slow，先让 fast 领先 slow 恰好 n 步。然后两个指针一起同速往前走，当 fast 走到末尾时，slow 正好停在倒数第 n 个节点的位置。
为什么？因为两个指针始终保持 n 的间距。当 fast 到达终点（末尾）时，slow 距离终点也正好是 n，那 slow 指向的不就是倒数第 n 个吗？
打个比方：两个人在跑道上，前面的人（fast）领先后面的人（slow）恰好 n 米，两人同速跑。当前面的人冲过终点线时，后面的人离终点线正好还剩 n 米。
一个细节：要删除节点，得站在它"前面" 在单链表里删除一个节点，需要拿到它的前一个节点 prev，然后执行 prev.next = prev.next.next 把它跳过去。
所以我们真正想让 slow 停的位置，不是"倒数第 n 个"本身，而是"倒数第 n 个的前一个"（也就是倒数第 n+1 个）。
实现上有个小技巧：让 fast 领先 slow 走 n+1 步，这样 fast 到末尾（null）时，slow 就停在待删节点的前一个了。
老朋友 dummy 又来了
如果要删的是头节点（比如 [1], n=1，删的是第一个也是唯一一个节点），那"前一个节点"就不存在了。老规矩，在头节点前面加一个 dummy 哨兵节点，让 slow 从 dummy 出发，这样即使删头节点也有"前一个"可用，不用特判。
图解整个过程(head = [1,2,3,4,5], n=2)
- 初始，加dummy，fast和slow都从dummy出发:
fast = dummy
slow = dummy
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
- 让fast先走n+1 = 3步
slow = dummy
fast = 3
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
现在fast和slow的间距是3.
- 两个指针一起走，直到fast变成null
slow = 3
fast = null (到null了，停)
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
现在slow停在节点3，它正好是待删除节点4(倒数第2个)的前一个。
- 删除
slow.next = slow.next.next // 3的next从4改成5
dummy -> 1 -> 2 -> 3 -> 5 -> null
返回dummy.next，结果是 1 -> 2 -> 3 -> 5
为什么是n+1步，而不是n步
如果fast先走n步，当fast到null的时候slow的位置正好是倒数第n个节点本身，这个时候只能拿到节点，删不了它。
因为要删除单链表节点必须站在它前面，所以我们要多走1步，让slow停在前一个的位置。
class ListNode(var `val`: Int) {
var next: ListNode? = null
}
class Solution {
fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
// 1. 哨兵节点，指向 head，统一处理"删除头节点"的边界情况
val dummy = ListNode(0)
dummy.next = head
// 2. 快慢指针都从 dummy 出发
var fast: ListNode? = dummy
var slow: ListNode? = dummy
// 3. 让 fast 先走 n+1 步，制造出 n+1 的间距
// 这样 fast 到达 null 时，slow 恰好停在"待删节点的前一个"
for (i in 0 until n + 1) {
fast = fast?.next
}
// 4. 两指针同速前进，直到 fast 走到末尾 (null)
while (fast != null) {
fast = fast.next
slow = slow?.next
}
// 5. 此时 slow 是待删节点的前一个，跳过待删节点完成删除
slow?.next = slow?.next?.next
// 6. 返回真正的头节点
return dummy.next
}
}
复杂度
- 时间复杂度: O(n)（这里 n 指链表长度）：fast 从头走到尾，一共只遍历一遍链表。相比"先数长度再删"的两遍遍历，双指针只需一遍。
- 空间复杂度: O(1)：只用了 dummy、fast、slow 几个指针，没有额外空间。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!