文章目录
可以看出时间复杂度为O(n)，所以解法中只能用一层循环，否则要超时。
解法一（快慢指针）：
**思路：**若要删除倒数第n个节点，则需让fast与slow之间始终保持n-1的间隔，这样fast到达最后一个节点的时候slow位于倒数第n-1+1+1个节点（n-1为间隔，1为fast所指的节点,1为slow及诶单本身）。
初始化的时候，fast、slow都指向head即第一个节点。让fast先走n步即n个next，这样才能使slow与fast间隔n-1。然后fast、slow同时一步一步走，直至fast->next==nullptr此时就可按照上图的方法删除倒数第n个节点了。
此时你可以得到下面的代码，和我们的预期输出相同。
但是直接提交会发现有个特例没有考虑到，如下：
正确代码如下：
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
ListNode* removeNthFromEnd(ListNode* head, int n) {
// write code here
ListNode *fast = head;
ListNode *slow = head;
//先让fast和slow之间保持n-1个间隔
while(n--) fast = fast->next;
//考虑特例
if(fast==nullptr) return head->next;
//fast、slow同时走
while(fast->next){
fast=fast->next;
slow=slow->next;
}
slow->next=slow->next->next;
return head;
}
};
解法二：
我们一次遍历不可能直接找到倒数第n个节点，因为我们不知道结尾在哪里，所以先遍历一次链表得到链表长度N后，根据图示找到其前驱，利用前驱删除目标节点。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
ListNode* removeNthFromEnd(ListNode* head, int n) {
// write code here
ListNode *p = head;
int N = 1;//p初始=head，所以算作一个节点
while(p->next){
p=p->next;
N++;
}
//特例判断
if(N-n==0) return head->next;
//前驱是正数第N-n个节点，所以向后移动N-n-1步
p=head;
for(int i = 0;i<N-n-1;i++) p=p->next;
p->next=p->next->next;
return head;
}
};