链表倒数第k节点

1. 题目描述

输入一个单链表，输出该链表中倒数第 k 个结点。

2. 思路描述

思路一：从头到尾遍历一遍，统计长度length。再从头遍历，直到length - k个节点停止，这就是倒数第 k 个节点。

思路二：只需要遍历一遍。准备 2 个指针a和b均指向第一个节点，a先移动k个位置；然后a和b一起向后移动，此时两个只指针的位置差为k；直到a移动到尾结点停止，此时b指向的节点就是倒数第 k 个节点。

3. 代码实现

下面是“思路二”的实现。

/**
 * 节点定义
 */
class Node {
  constructor(value, next) {
    this.value = value;
    this.next = next;
  }
}

/**
 * 寻找倒数第k个节点
 * @param {Node} head 初始节点
 * @param {Number} k 顺序(倒数)
 */
function findKthFromTail(head, k) {
  if (!head || k <= 0) {
    return null;
  }

  let a = head,
    b = head;

  for (let i = 0; i < k; ++i) {
    a = a.next;
    if (!a) {
      return null;
    }
  }

  while (a) {
    b = b.next;
    a = a.next;
  }

  return b;
}

/**
 * 以下是测试代码, 分别输出倒数第2、3和5个节点
 */

let node3 = new Node(3, null),
  node2 = new Node(2, node3),
  node1 = new Node(1, node2),
  head = new Node(0, node1);

console.log(findKthFromTail(head, 2));
console.log(findKthFromTail(head, 3));
console.log(findKthFromTail(head, 5));

大师兄

1. 题目描述

2. 思路描述

3. 代码实现