描述

给定一个链表，删除链表的倒数第n个节点并返回链表的头指针

例如: 给出的链表为 1 - 2 - 3 - 4 - 5 n = 2 删除了链表的倒数第2个节点之后，链表变为: 1 - 2 - 3 - 5

备注： 题目保证n一定是有效的 请给出时间复杂度为O(n)的算法

示例：

输入：{1, 2} 2
返回值 {2}

解题思路:双指针

我们也可以在不预处理出链表的长度，以及使用常数空间的前提下解决本题。

由于我们需要找到倒数第 n 个节点，因此我们可以使用两个指针 first 和 second 同时对链表进行遍历，并且 first 比 second 超前 n 个节点。当 first 遍历到链表的末尾时，second 就恰好处于倒数第 n 个节点。

具体地，初始时 first 和 second 均指向头节点。我们首先使用 first 对链表进行遍历，遍历的次数为 n。此时，first 和 second 之间间隔了 n-1 个节点，即 first 比 second 超前了 n 个节点。

在这之后，我们同时使用 first 和 second 对链表进行遍历。当 first 遍历到链表的末尾（即 first 为空指针）时，second 恰好指向倒数第 n 个节点。

如果我们能够得到的是倒数第 n 个节点的前驱节点而不是倒数第 n 个节点的话,删除操作会更加方便。

因此我们可以考虑在初始时将 second 指向哑节点，其余的操作步骤不变。这样一来，当 first 遍历到链表的末尾时，second 的下一个节点就是我们需要删除的节点。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  // 创建虚拟头结点
  let dummy = new ListNode(0);
  // 将虚拟头结点和链表连接
  dummy.next = head;
  // 初始化first 指向头节点
  let first = head;
  // 初始化 second 指向 虚拟头节点 这样first 就领先了
  let second = dummy;
  
  // 开始遍历链表 走 n 步
  for (let i = 0; i < n; i++) {
    first = first.next;
  }

  while (first !== null) {
    first = first.next;
    second = second.next;
  }
  // 退出循环的时候 second 正好是在需要删除链表的前一个
  second.next = second.next.next;
  // 头结点
  let ans = dummy.next;
  // 返回
  return ans;
};