删除链表的倒数第 N 个结点

题目：

　　给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗？

题解：

　　看到题目首先想到的时候想到数组，因为数组删除第N个数的时间复杂度是O(1)。但是链表的存储空间不是连续的，无法通过下标直接定位到某个元素，链表的查询、删除都要一个一个节点遍历，查询删除时间复杂度是O(n)。首先遍历一次求出链表的长度length，再遍历一次删除第length-n+1个节点。但是题目要求我们使用一趟遍历，那么我们使用快慢指针，快指针先走，走了n步时，慢指针再走，那么当快指针走到尾结点时，慢指针slow.next就是倒数第n个节点。下面上代码：

Java版本：

public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null) return null;
        //虚拟头结点
        ListNode dummy = new ListNode();
        dummy.next = head;
        //快指针
        ListNode slow = dummy;
        //慢指针
        ListNode fast = dummy;
        slow.next = head;
        fast.next = head;
        //快指针先走n步
        for(int i=1;i<=n;i++){
            fast = fast.next;
        }
        //慢指针再走
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }

JS版本：

var removeNthFromEnd = function(head, n) {
    var dummy = new ListNode();
    dummy.next = head;//头指针
    //两个指针指向头指针
    var i = dummy;
    var j = dummy;
    for(var m = 0;m<n;m++){//i指针向后移动n位
        i = i.next;
    }
    while(i.next != null){//i指向最后一个节点：i.next = null;
        i = i.next;
        j = j.next;
    }
    //删除倒数第N个节点
    j.next = j.next.next;
    
    return dummy.next;
};