// 时间复杂度: O (n)

// 空间复杂度: O (1)

class Solution {

public:

    ListNode* removeNthFromEnd(ListNode* head, int n) {

        ListNode* dummyHead = new ListNode(0);

        dummyHead->next = head;

        ListNode* slow = dummyHead;

        ListNode* fast = dummyHead;

        while(n-- && fast != NULL) {

            fast = fast->next;

        }

        fast = fast->next; //fast 再提前走一步，因为需要让 slow 指向删除节点的上一个节点

        while (fast != NULL) {

            fast = fast->next;

            slow = slow->next;

        }

        slow->next = slow->next->next; 

        // ListNode *tmp = slow->next;  C++ 释放内存的逻辑

        // slow->next = tmp->next;

        // delete nth;

        return dummyHead->next;

    }

};