[LeetCode] 19. 删除链表的倒数第 N 个结点
题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 ：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
解题思路：
使用一趟扫描实现。这里就是双指针的经典应用。如果要删除倒数第n个节点，让fast移动x步，然后让fast和slow同时移动，直到fast指向链表末尾的下一个结点nullptr，这时候大家才会停下来。
那么问题来了，应该是先让fast指针移动多少步才合理呢。
首先，我们使用虚拟头结点，这样方便处理删除实际头结点的逻辑。
那么，快慢指针都是从虚拟头结点出发的。使用上图的例子，也添加虚拟头结点，那一共有5个结点（虚拟头结点不算是结点）。要让fast指针走到nullptr,那需要走6(5+1)步。而要慢指针走到被删除的结点的前一结点停下来，那需要slow指针走3（5-2）步。
一般化：
那么，设一共有k个结点，那fast指针走到nullptr,那需要走k+1步。slow指针要走到被删除的结点的前一结点，需要走(k-n)步。
一开始，假设fast指针先走x步，接着fast,slow指针同时走，而slow指针走（k-n）步，就停下来，而fast指针也就跟着走(k-n)步就走到了nullptr。
所以k+1=(k-n)+x; x=n+1;
所以fast指针需要先走n+1步。
理解了这个，代码就好写了。
代码：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
auto dumyhead=new ListNode(0,head);
auto fast=dumyhead;
for(int i=0;i<=n;++i)
fast=fast->next;
auto slow=dumyhead;
while(fast){
fast=fast->next;
slow=slow->next;
}
//这里没有写到delete 结点
slow->next=slow->next->next;
return dumyhead->next;
}
};