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

/**
 * @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
};

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]

/**
 * @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)
};