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

[louzhedong]

题目

出处：LeetCode 算法第19题

给定一个链表，删除链表的倒数第 *n *个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

思路

由于只能实现一遍扫描，所以我们可以使用两个指针，让一个指针先走一定的步数，使两个指针之间间隔n步，当前面的指针移动到链表尾部的时候，后面的指针刚好处于要删除的节点的前面，将它的next指向next.next就可以了。为了处理删除第一个节点的情况，我们在链表头部新建一个节点，使其指向第一个节点。

实现

var removeNthFromEnd = function(head, n) {
    var result = new ListNode(0);
    result.next = head;
    var second = result;
    while(n > 1) {
        head = head.next;
        n--;
    }
    while(head.next != null) {
        head = head.next;
        second = second.next;
    } 
    second.next = second.next.next;
    return result.next;
};