[力扣_19] 删除链表的倒数第 N 个结点
题目入口：点击进入
相关算法：
- 双指针(快慢指针)——时间复杂度O(len)，len为链表长度，空间复杂度O(1)
- 栈的应用——时间复杂度O(len+n)，空间复杂度O(len)
- 暴力破解——时间复杂度O(len+n)，空间复杂度O(1)
思路和算法：
这道题之所以是中等难度，是因为它多了一个附加条件：只能有一次遍历，则我们上述提供的三个解法中只有一个符合要求，那就是快慢指针
有个很重要的new技能，叫做哑结点，在未附有头结点的链表下，我们可以新增一个头结点，这样就可以对所有情况做一个统一处理，而不需要处理若删除在头端的头指针变换的特殊情况。
在本题中，我们附设一个结点，让它的next指向head。
其余两个在官方题解中能过，因为都不难，而且为了更符合题意，我们只对快慢指针做记录，其余只提供简单思路：
栈的应用——栈具有先进后出的特点，我们可以依次将结点压入栈中，然后退回到第n个结点的时候，记录下n->next结点的值，然后再退回到n的前驱，让n的前驱指向n的后继，即可完成删除，在C语言里面，需要利用动态数组的思想，对每一个压入的结点都realloc重新分配空间，实现较为麻烦。
暴力破解——我们可以先从头端出发，遍历一遍链表，得到链表长度，再从头端出发，走到n的位置，让n的前驱指向后继，完成删除。
快慢指针
快慢指针在之前线性表的题解中我们就不陌生了，快指针相当于一个侦察兵，去前端探查情况然后让慢指针依照情况进行处理
同样，我们从题意可知，我们需要找到n结点的前驱，然后让前驱指向n结点的后继，来完成删除操作，具体思路如下：
- 假设设定了双指针p和q的话，当q(快指针)达到末尾的NULL时，p与q之间相隔的元素个数为n的时候，那么删掉p的下一个指针就完成了要求
- 设立哑结点(代码中为dim)指向head
- 设定双指针p和q，初始都指向哑结点
- 移动快指针q，设立计数变量k，k随着q后移递增
- 当k>=n时候，慢指针开始移动
- 当q为空时，将p的下一个结点指向它的下下个结点
- 返回哑结点的->next（防止删除的是头结点。）
代码如下所示：
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
if(head->next==NULL&&n==1) return NULL;
struct ListNode*dim=(struct ListNode*)malloc(sizeof(struct ListNode));//哑结点
dim->next=head;
int k=0;//计数变量
struct ListNode*left=dim,*right=head;
while(right)
{
if(k>=n)//移动慢指针
left=left->next;
right=right->next;
k++;
}
left->next=left->next->next;
return dim->next;
}