leetcode 删除链表的倒数第N个节点（每日计划）

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

示例：

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

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

说明：

给定的 n 保证是有效的。

进阶：

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

我的算法实现：

/**
 * 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 p = head;
  let arr = [];
  let i = 0;
  while (p !== null) {
    arr[i++] = p;
    p = p.next;
  }
  if (arr[i - n - 1]) {
    arr[i - n - 1].next = arr[i - n].next;
    arr[i - n].next = null;
  } else {
    return arr[i - n].next;
  }
  return head;
};

1. 先将所有的节点保存到数组中；
2. 循环结束后，数组长度 - n 得到了要删除的节点，由于 n 保证有效，所以这个一定有值；
3. 让上一个节点指向要删除节点的下一个节点，无论有没有；
4. 如果要删除的节点是第一个节点，就直接返回要删除节点的下一个节点即可。

官方解法：删除链表的倒数第N个节点

其中我最看好的是双指针法。两个指针直接的距离刚好就是 n 的长度，这样如果快指针到头了，那么只需要删除慢指针的后继即可成功。

这个方法和我的方法最大的不同是，在最小的空间开销下完成了任务。而我的前后需要开辟大量空间，虽然从时间复杂度来差不多，但空间就浪费很多。

还有一种递归写法，递归写法我也想过，但是就是不知道怎么操作，感觉不行，所以最终放弃了。

const removeNthFromEnd = (head, n) => {
  // 1. 设置倒数节点
  let lastN = 0;

  // 2. 设置递归
  const recursion = (head) => {

    // 2.1 如果抵达链表尾，返回 null
    if (!head) {
      return null;
    }

    // 2.2 设置 next 表示下一个节点
    const next = recursion(head.next);

    // 2.3 每次递归的【归】环节，lastN + 1
    lastN++;

    // 2.4 如果 lastN 和 n 相同，则进行删节点操作
    if (lastN === n) {
      head = next;
    }

    // 2.5 再【归】一层后，修正 next 指向
    if (lastN === n + 1) {
      head.next = next;
    }

    // 2.6 返回最终节点
    return head;
  };

  // 3. 调用递归
  return recursion(head);
};
作者：jsliang
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/javascript-di-gui-die-dai-2-chong-jie-fa-xiang-jin/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---

来源：力扣（LeetCode）