[数据结构与算法]删除链表中倒数第N个节点

题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？
示例 ：解题思路：
方法一：先统计节点总数count，然后算出倒数第n个数为正数count - n + 1，最后正向迭代删除指定位置的节点。

注意：1、正向计数为不是count - n + 1 ，不要误用count - n来移动。
2、删除节点，要找的是该节点的前一个节点。如果创建了dummyNode虚节点（建议使用），那么移动了count - n + 1恰好dummy就是删除节点的前一个节点，只需要执行dummy.next = dummy.next.next即可。（C++需要释放节点的空间）。
3、维护节点变量，这一点很重要，该方法需要一个节点变量进行计数，一个节点变量进行删除操作，还需要一个节点作为链表的头结点返回**（返回的头结点一定其实就是拷贝一个操作链表的节点，如果操作链表的节点是虚节点，返回时需要.next指向头结点）**。

方法二：进阶要求的实现。一次扫描，只靠一个逆序的n肯定是不够的，链表和数组扫描过程中最大的不同就是链表不存在准确的临界变量，只有一个链表结束标志 节点.next == null。因此给我们的条件有两个，一个是倒数第n个位置和链表末尾，通过双指针利用两个条件的相对位置即可通过一次遍历完成本题。
注意：该方法和上面一样，需要注意维护节点变量，该方法需要两个节点变量进行扫描（一个判断是否到队尾，一个用来找到对应位置执行删除操作），还需要一个节点作为链表的头结点返回。

时间复杂度：
方法一：虽然方法一是两次扫描，方法二是一次扫描。但是数量级都是L（L为链表长度），因此时间复杂度为O(L)。
空间复杂度：O(1)。

答案代码：
方法一：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //head会用来计数，并且head可能会被删除，因此不能返回
        //dummy后面会执行操作，因此也不能返回
        //因此需要定义ans，为答案返回做准备
        ListNode ans = dummy;
        int count = 0;
        while(head != null)
        {
            count++;
            head = head.next;
        }
        for(int i = 0 ;i < count - n ;i++)
        {
            dummy = dummy.next;
        }
        dummy.next = dummy.next.next;
        //注意最后一步不能返回head
        return ans.next;
    }
}

方法二：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyFast = new ListNode(0,head);
        ListNode dummySlow = new ListNode(0,head);
        //其他两个dummy都要移动，head可能被删除
        //因此返回值要单独定义，并且连接的是新链表dummySlow
        ListNode dummyAns = dummySlow;
        for(int i = 0; i < n ; ++i)
        {
            dummyFast = dummyFast.next;
        }
        while(dummyFast.next != null)
        {
            dummyFast = dummyFast.next;
            dummySlow = dummySlow.next;
        }
        dummySlow.next = dummySlow.next.next;
        
        return dummyAns.next;
    }
}