给你一个链表，删除链表的倒数第 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 个节点，关键在于找到待删除节点的前驱节点。用一趟扫描解决的核心技巧是快慢指针（或称前后指针）：

创建虚拟头节点 dummy_head，使其 next 指向原链表 head，并让 fast 和 slow 指针都从 dummy_head 出发；
fast 先走 n + 1 步（多走一步是为了让 slow 最终指向待删除节点的前驱，而非节点本身）；
然后 fast 和 slow 同步前进，直到 fast 走到 None（链表末尾）；
此时 slow 正好指向倒数第 n 个节点的前驱节点，执行 slow.next = slow.next.next 即可删除目标节点；
返回 dummy_head.next。

时间复杂度 O(n)，空间复杂度 O(1)。

关键直觉：快指针比慢指针多走 n + 1 步，两者之间的距离就是 n + 1。当快指针走到尽头，慢指针自然离尽头也有 n + 1 的距离，即慢指针指向倒数第 n + 1 个节点，刚好是倒数第 n 个节点的前驱。

解法一（双指针法）

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy_head = ListNode(0, head)
        fast = slow = dummy_head

        # fast 先走 n + 1 步，确保 slow 将来停在待删除节点的前驱
        for _ in range(n + 1):
            fast = fast.next

        # 同步后移，直到 fast 走到链表末尾
        while fast:
            fast = fast.next
            slow = slow.next

        # 此时 slow 指向倒数第 n 个节点的前驱，执行删除
        slow.next = slow.next.next

        return dummy_head.next

解释一（双指针代码解释）

代码片段	作用与原因
`dummy_head = ListNode(0, head)`	创建虚拟头节点，统一处理删除头节点的情况（如 n == 链表长度时）
`fast = slow = dummy_head`	快慢指针初始化为虚拟头节点
`for _ in range(n + 1): fast = fast.next`	fast 先走 n+1 步，建立 "间隔 n+1" 的间距。多走 1 步是为了让 slow 指向待删除节点的前驱
`while fast: fast = fast.next; slow = slow.next`	快慢指针同步移动。fast 走到 None 时，slow 恰好指向倒数第 n 个节点的前驱
`slow.next = slow.next.next`	跨过待删除节点，完成删除
`return dummy_head.next`	返回虚拟头节点的 next，即删除后链表的新头节点

思路二（计算长度法 / 两趟扫描）

朴素解法：先遍历一遍确定链表长度 L，则倒数第 n 个节点就是正数第 L - n + 1 个节点。第二趟遍历到第 L - n 个节点（即待删除节点的前驱），执行删除即可。

解法二（两趟扫描）

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # 计算链表长度
        length = 0
        cur = head
        while cur:
            length += 1
            cur = cur.next

        dummy_head = ListNode(0, head)
        cur = dummy_head
        # 走到待删除节点的前驱（第 length - n 个位置，从 0 开始计数）
        for _ in range(length - n):
            cur = cur.next

        cur.next = cur.next.next
        return dummy_head.next

解释二

代码片段	作用与原因
`while cur: length += 1; cur = cur.next`	第一趟：遍历链表，统计节点总数
`for _ in range(length - n): cur = cur.next`	第二趟：走到待删除节点的前驱（第 L-n 个位置）
`cur.next = cur.next.next`	跨过待删除节点，完成删除

19. 删除链表的倒数第N个节点