删除链表的倒数第N个结点---快慢指针

题意

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

样例

示例 1：

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

示例 2：

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

思路

类似于滑动窗口的想法，双指针

p和q指针维持一定的距离可以找到被删除的点前一个点和后一个点

先运行q指针到n+1,从自定义的头结点开始。

然后p指针和q指针一起移动，移动的条件是q指针不为NULL.

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode * VitualHead = new ListNode(0);
        VitualHead->next=head;
        ListNode * p = VitualHead;
        ListNode * q = VitualHead;
        for (int i = 0;i < n + 1;i ++){//有点类似滑动窗口，先维持一个具体的间隔
            q = q->next;
        }
        while (q){
            q = q->next;
            p = p->next;
        }
        ListNode * deln = p->next;
        p->next = deln->next;
        delete deln;
        return VitualHead->next;

    }
};