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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

题目要求一次遍历，可以使用双指针法。首先设置虚拟节点 dummy 指向 head，设定双指针 p 和 q ，开始都指向虚拟节点 dummy；将 p 先向后移动 n+1 个结点，然后 p 和 q 同时向后移动，直到 p 指针指向空，即 p 与 q 之间相隔的元素个数为 n，q 的下一个结点就是倒数第 n 个结点，此时删除 q 指向的下一个结点，也就是将 p 的下一个节点指向下下个节点即可。

时间复杂度：O(n)。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy ->next = head;
        ListNode* p = dummy;
        ListNode* q = dummy;

        for (int i = 0; i <= n; i++)
            p = p -> next;

        while (p) {
            p = p -> next;
            q = q -> next;
        }
        q -> next = q -> next -> next;

        return dummy -> next;
    }
};