给你一个链表，删除链表的倒数第 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]
?
正解
1)两次历遍：先手历遍一次获得size大小，在结合倒数n，算出目标节点的下标，之后进行删除节点操作
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode virtual = new ListNode(0);
virtual.next = head;
ListNode temp=virtual;
int size = 0;
int index;
ListNode ret=virtual;
while (temp.next != null) {
size++;
temp=temp.next;
}
index = size - n + 1;
for (int i = 0; i < index-1; i++) {
virtual = virtual.next;
}
if (virtual.next != null && virtual.next.next != null) {
virtual.next =virtual.next.next;
} else {
virtual.next = null;
}
return ret.next;
}
}2）双指针一次历遍：如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
-
定义fast指针和slow指针，初始值为虚拟头结点，如图：
-
fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：?
-
fast和slow同时移动，之道fast指向末尾，如题：?
-
删除slow指向的下一个节点，如图：?
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode virtual = new ListNode(0);
virtual.next = head;
ListNode fast=virtual;
ListNode low=virtual;
int size=0;
while (fast.next!=null){
fast=fast.next;
size++;
if(size>n){
low=low.next;
}
}
if(low.next.next!=null){
low.next=low.next.next;
}else {
low.next=null;
}
return virtual.next;
}
}