链表倒数第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))