19.删除链表的倒数第n个节点

题目地址：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
题解地址：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/jsshi-xian-yi-tang-sao-miao-lian-biao-to-9ee9/

前言

在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 \textit{next}next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题思路

正常解题思路：
从题目要求来说，因为不知道链表的总长度，所以我们需要先扫描一遍，得到链表的size；然后第二次扫描链表，到达size-n处结点时，因为他后边的结点是需要删除的，所以我们将他的next指向他下一个节点的next。
（示例1中，size为5，要删除倒数第2个，我们就要找到5-2也就是第三个）

不按常理出牌的思路：
扫描链表我们可以用迭代（while）也可以用递归，当我们用递归的时候，你可以想想洋葱模型了，递进进去以后、到达尾结点后，他总要回来的嘛！
我们就可以利用JS解释性语言的特点，在不同的行数巧妙地执行 “求链表长度” 以及 “删除倒数节点” 的逻辑。

代码块三部分：
1、在他递归进入时，我们累加计数器，得到链表的长度，并且记录要删除的目标元素的前一个节点位置值（size-n）
2、在他递归出来时，我们递减计数器，当计数器与1中记录的节点位置相同时，说明我们来到了要删除节点的其一个节点上，此时执行节点删除操作即可。
3、因为可能删除第一个节点，所以我们需要在head节点前增加一个哑结点，用来实现只有1个节点、且要删除倒数第一个节点的情况。

链表结构

递归流程图解

代码

/**
 * 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) {
  if (!head) return head
  let size = 0,
    target = 0,
    preHead = new ListNode(-1, head) // 3 准备一个哑结点
  function getNum(node) {
    // 1 根据node是否存在，得到链表长度
    if (!node) {
      target = size - n
      return size // 递归到头，返回链表总长度
    }
    size++ // 类增计数器
    // 2 递归，并在递归后得到 递归后倒数的值
    let backwardNum = getNum(node.next)
    if (backwardNum === target) node.next = node.next.next // 执行删除操作
    return --backwardNum // 递减计数器
  }
  getNum(preHead)
  return preHead.next
};