题目描述
给你一个链表，删除链表的倒数第 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 <= 30
0 <= Node.val <= 100
1 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
解题思路
首先是可以用遍历2遍的方法来求结果的。
第一遍遍历得到有多少个节点，就可以得到是正序的第几个节点。
我们不用上面的方法，我们用遍历一边的方法。
双指针的方法——快慢双指针
先让快指针走n步，然后快慢指针同时移动，当快指针走到空的时候，要删除的节点就是慢指针的下一个节点。
因为可能会删除头节点，所以我们设一个带头的节点。（为了方便处理）
代码
/** * 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* temp=new ListNode; temp->next=head; ListNode* f,*s; f=s=temp; //快指针先走 for(int i=1;i<=n;i++) f=f->next; //一起走 while(f->next) { f=f->next; s=s->next; } //删除 ListNode* cur=s->next; s->next =cur->next; delete cur; //删除我们定义的头 cur=temp->next; delete temp; //返回结果 return cur; } };
