https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

<aside> 💡

思路：设计两个指针（快慢指针），让两者中间相隔n个节点。再让右侧指针指向链表尾后节点（即一个空节点），则左侧节点的下一节点即是倒数第N个节点

由于需要涉及对节点的操作（删除节点），所以需要设置虚拟头节点

</aside>

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummyHead = new ListNode();
    dummyHead->next = head;

    ListNode* slow = dummyHead;
    ListNode* fast = dummyHead;

		// 快指针移动n步
    for (int i = 0; i < n; ++i) {
        fast = fast->next;
    }

		// 让快指针向前移动，直到fast->next指向尾后
		// 慢指针同步移动
    while (fast->next) {
        slow = slow->next;
        fast = fast->next;
    }

		// 此时慢指针指向的就是倒数第n个节点
    ListNode* tmp = slow->next->next;
    delete slow->next;
    slow->next = tmp;

    head = dummyHead->next;
    delete dummyHead;
    return head;
}