19. 删除链表的倒数第 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

**进阶：**你能尝试使用一趟扫描实现吗？

快慢指针，虚拟节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建一个虚拟头节点，其next指向实际的头节点
        // 使用虚拟头节点简化边界条件的处理，尤其是当需要删除的是列表的头节点时
        ListNode dummy = new ListNode(0, head);
        
        // first指针初始化为头节点
        ListNode first = head;
        // second指针初始化为虚拟头节点。慢指针是构建节点。
        ListNode second = dummy;
        // first指针先向前移动n步，一开始快指针快了1步，现在又走了n步，所以此时快指针比慢指针多走了1+n步，
        // 当first到达null时，second在倒数第n+1个节点处，即要删除的节点的前一个节点。
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        
        // 然后，first和second指针同时移动，直到first指针到达链表末尾（null）
        // 这时，second指针将指向倒数第n个节点的前一个节点
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        
        // second指针的下一个节点就是需要删除的节点
        // 因此，将second的next指向second的next的next，从而跳过了需要删除的节点
        second.next = second.next.next;
        // 返回处理后的链表的实际头节点，即虚拟头节点的next节点
        return dummy.next;
    }
}

• 时间：O(L)，其中 $L$ 是链表的长度。
• 空间：O(1)