1. 题目描述

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

2. 思路描述

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

思路二:只需要遍历一遍。准备 2 个指针ab均指向第一个节点,a先移动k个位置;然后ab一起向后移动,此时两个只指针的位置差为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
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50