19. 删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点
分析
首先因为链表头节点可能被删除，因此得用虚拟头节点法。这个很容易想到。
一个思路是用递归的方式从后往前开始计数，找到倒数第 N+1 个节点，进行删除。因为我们有虚拟头节点，所以即使 n=1，N+1 也是有对应节点的。
有没有更高级的办法呢？有！固定间隔距离的双指针。
双指针法的思路很简单，首先我们将虚拟头节点的位置定义为 1，创建一个 fast 指针，从头往后移动 n 次，然后这个 fast 所在的位置就是 n+1,反过来倒着计数，假设 fast 指针的位置为 1 的话，那么虚拟头节点就是 n+1，然后我们再创建一个在虚拟头节点的 slow 指针，接着同步移动 slow 和 fast 这两个指针，那么当 fast 指向链表的最后一个元素的时候（fast.next==null），slow 指向的就是倒数第 n+1 个节点，也就是待删除节点的前一个结点。
这个双指针法的精髓是让两个指针保持固定的距离，首先添加一个虚拟头节点，然后先把快指针移动 n 次，此时 slow 和 fast 就间隔 n，然后再同时移动快指针和慢指针，直到快指针移动到链表的最后一个元素。非常巧妙
解题
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyNode = new ListNode(-1,head);
removeNode(dummyNode,n);
return dummyNode.next;
}
// 递归主要用来计数
public int removeNode(ListNode head,int n) {
if(head.next==null){
return 1;
}else{
int reverseIndex = removeNode(head.next,n)+1;
if(reverseIndex==(n+1)){
head.next = head.next.next;
}
return reverseIndex;
}
}
双指针法的实践，确实很简单，很高级
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode fastNode = dummyHead;
// nowIndex 的定义是fast当前所在位置，位置的从1开始定义
int nowIndex = 0;
// 先移动快指针
while (nowIndex < n && fastNode != null) {
fastNode = fastNode.next;
nowIndex++;
}
// 退出循环的时候，nowIndex比n小，说明没到n，fastNode 就为null了，也就是说链表没那么长
if (nowIndex < n){
// 没有那么长
return head;
}
// 指向要删除节点的前一个节点
ListNode slowPreNode = dummyHead;
while(fastNode != null && fastNode.next != null){
// 同时移动
fastNode = fastNode.next;
slowPreNode = slowPreNode.next;
}
//删除
slowPreNode.next=slowPreNode.next.next;
return dummyHead.next;
}