LeetCode题解：剑指 Offer 22. 链表中倒数第k个节点，递归，JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

解题思路：

1. 递归其实分为两个过程，即逐层下探到底部，遇到终止条件后再逐层退出，例如下面这段代码：

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
  if (!head) {
    return head
  }

  console.log('enter', head)
  const node = getKthFromEnd(head.next, k)
  console.log('out', head)

  return node
};

当输入[1,2,3,4,5]时，可以看到打印结果：

enter [1,2,3,4,5]
enter [2,3,4,5]
enter [3,4,5]
enter [4,5]
enter [5]
out [5]
out [4,5]
out [3,4,5]
out [2,3,4,5]
out [1,2,3,4,5]

2. 根据递归遍历顺序，只需要在逐层退出递归时，进行计数。遇到倒数第k个节点时，将其返回即可。

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */

// 该代码在本地调试可以通过，提交之后会在用例`[1]\n1`报错
// 实际提交可以参考第二个Tab中的代码，是可以提交成功的

let count = 0 // 用于统计倒数的个数

var getKthFromEnd = function(head, k) {
  // 递归终止条件，遇到链表尾部，即空节点时退出
  if (!head) {
    return head
  }

  // 递归遍历链表
  const node = getKthFromEnd(head.next, k)

  // 在递归逐层退出时计数
  count++
  // 计数到倒数第k个节点时，将当前节点作为结果返回
  // 它会随着递归的退出返回到最外层
  if (count === k) {
    return head
  }

  // 讲逐层递归遍历的节点返回
  return node
};

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
  if (!head || !head.next) {
    return head
  }
  let count = 0

  function recursion(head, k) {
    if (!head) return head
    const node = recursion(head.next, k)
    count++
    if (count === k) {
      return head
    }

    return node
  }
  return recursion(head, k)
};