力扣题目链接

给你一个链表，删除链表的倒数第 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]

---

第一想法就是要是知道链表长度就好了吧

暴力解法就是先遍历完确定链表长度 然后再遍历一遍，时间复杂度O（2nums.length - n）

---

其实双指针方法就是提取 暴力解法的核心思想：

在暴力解法里面，两次遍历是在两个时间线上的（两个for循环里面）

优化成一个for循环，就是优化到一个时间线上

那么，就从一个时间线上思考（同时进行两次遍历的感觉）

我们暴力解法之所以第一次指针ptr1的循环是为了得到nums.length，之后ptr1就在tailNode等着ptr2进行（nums.length - n）的遍历

那么在一个时间线上，就是ptr2 慢了 ptr1 有n个元素的遍历 这样一个速度（这里引入 物理速度的概念只是为了自圆其说，这里假设的是ptr1 和 ptr2同一时间同一起点出发）

相对来说，就是ptr1 快了 ptr2 有n个元素的遍历（这里不用速度的概念，是因为从结果来看，ptr1就只是比ptr2在同一时间段内就是多遍历了n个元素）

那么ptr1先遍历n个元素，ptr2再开始遍历，到最后结果就是一样的，ptr2还是会指向target

因为要删除target，那么ptr2实际要指向target前一个节点，那么ptr1就要先再多遍历一个元素（先遍历n + 1个元素）

而且如果要删除的是实际头节点，就要额外处理它，所以依旧使用虚拟头节点（这里也是多了一次移动下一个节点的操作，由于上文思路是ptr1最后在tailNode就停下循环，那么这多一次的操作可以   再多遍历一个节点，但是这样有点绕， 其实就可以ptr1遍历到null也可以实现，下面给出的代码就是这样）

---

Java代码：

/**
 * 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 dummyHead = new ListNode(-1, head);
        ListNode fast = dummyHead;
        ListNode slow = dummyHead;

        // 从结果来看，fast比slow多遍历n个元素
        // 因为slow要指向target前一个节点
        // 所以fast再多遍历一个节点
        for(int i = 0; i < n + 1; i++)
            fast = fast.next;

        // 这时slow 和 fast同时出发
        // 最后fast遍历到tailNode，slow遍历到target的前一个节点
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 删除target
        slow.next = slow.next.next;

        return dummyHead.next;
    }
}