难度中等2380
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]示例 2：
输入：head = [1], n = 1
输出：[]示例 3：
输入：head = [1,2], n = 1
输出：[1]提示：
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
**进阶：**你能尝试使用一趟扫描实现吗？
解题思路：快慢指针
这道题就是寻找链表中倒数第 n 个结点的一个拓展题目（这里认为是已经懂了快慢指针的思想），一开始我的思想就是用 fast 来代表快指针，然后 cur 代表慢指针，也就是最后 cur 到达了倒数第 n 个节点，在遍历同时用 pre 记录 cur 的前驱节点，最后将前驱节点 pre 和 cur 的后继节点链接起来即可！为了避免一些空指针判断，这里代码中加入了哨兵位节点 tummy ！
/**
* 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* tummy = new ListNode(-1, head);
ListNode* pre = tummy;
ListNode* cur = head;
ListNode* fast = head;
// 快慢指针思想让cur到达倒数第k个结点
while(fast != nullptr && n > 0)
{
fast = fast->next;
n--;
}
while(fast != nullptr)
{
fast = fast->next;
cur = cur->next;
pre = pre->next;
}
// 此时cur为倒数第k个结点，pre为前驱节点，将cur删掉
pre->next = cur->next;
delete cur;
ListNode* newhead = tummy->next;
delete tummy; // 释放哨兵节点
return newhead;
}
};优化版本
看了题解之后发现其实我们不一定要让 cur 走到倒数第 n 个节点，我们只需要让它走到倒数第 n 个节点的前驱节点，也就是说我们不需要使用 pre 来记录前驱节点了，cur 此时就是前驱节点，直接将倒数第 n 个节点删除即可（也就是链接后继节点）！
详细的看代码：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* tummy = new ListNode(-1, head); // 哨兵位节点
ListNode* cur = tummy; // 注意细节，让cur在tummy处开始是为了防止如果是删除第一个节点的情况
ListNode* fast = head;
// 快慢指针思想让cur到达倒数第k个结点的前驱节点
while(fast != nullptr && n > 0)
{
fast = fast->next;
n--;
}
while(fast != nullptr)
{
fast = fast->next;
cur = cur->next;
}
// 此时cur为倒数第k个结点的前驱节点，将cur->next删掉
// 实际上不用判断next是否为空，因为fast一直都是在cur的右边两节点外的距离（包括fast为空），并且题目说明节点个数大于1，所以next不会为空
ListNode* next = cur->next;
cur->next = next->next;
delete next;
ListNode* newhead = tummy->next;
delete tummy; // 释放哨兵节点
return newhead;
}
};