LeetCode19-删除链表的倒数第N个节点
最近全国疫情严重，待在家里没事干，马上又要准备春招了，最近刷刷题，记录一下！再说一句，武汉加油，大家出门记得戴口罩！
1、题目
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
2、思路
使用双指针解法，定义两个指针：first和second，
第一个指针(first)先从链表的开头向前移动 n步，
然后first和second同时向后移动，我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。
Tips：定义一个虚拟头结点，因为原来的头结点可能被删除，引入虚拟头结点后可以处理头结点被删除的情况，代码中少一些判断。如图所示。
3、代码
c++
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
//定义虚拟头结点,指向head
auto dummy=new ListNode(-1);
dummy->next=head;
//定义两个指针
auto first=dummy,second=dummy;
//first指针先走n步
while(n--) first=first->next;
//first和second指针同时走，直到first走到终止为止
while(first->next)
{
first=first->next;
second=second->next;
}
second->next=second->next->next;
return dummy->next;
}
};
Java
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//定义虚拟头结点,指向head
ListNode dummy=new ListNode(-1);
dummy.next=head;
//定义两个指针
ListNode first=dummy,second=dummy;
//first指针先走n步
for (int i = 1; i <= n; i++) {
first = first.next;
}
//first和second指针同时走，直到first走到终止为止
while(first.next!=null)
{
first=first.next;
second=second.next;
}
second.next=second.next.next;
return dummy.next;
}
}