时间o(n) 空间o(1)

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //开辟一个虚节点防止删头
        auto vnode = new ListNode(0);
        vnode->next = head;
        auto p = vnode, q = vnode;
        //双指针求倒数第k个节点 快指针快走k+1步 
        for(int i =0; i < n + 1; ++i) {
            p = p->next;
        }
        //然后两个指针一起走 快指针走到头 慢指针的下一个就是要删除的节点
        while(p) {
            p = p->next;
            q = q->next;
        }
        //删除目标节点
        q->next = q->next->next;
        return vnode->next;
    }
};