链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

解题思路

我们无法逆序遍历链表，就很难得到链表的倒数第k个元素，但是我们可以反过来考虑，如果当前处于正数第k+1的位置上，即距离链表头部的距离是k，有一个指针fast，还有一个指针指向头部slow;此时二者同步向前移动，当fast指针走到尾部的时候，两个指针之间的距离还是k。此时走的慢的指针slow正好处于倒数第k的位置上

具体步骤拆分如下：

• step 1：准备一个快指针，从链表头开始，在链表上先走k步。
• step 2：准备慢指针指向原始链表头，代表当前元素，则慢指针与快指针之间的距离一直都是k。
• step 3：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数k个元素的位置。

var getKthFromEnd = function(head, k) {
    let fast = head
    let slow = head;
    while (fast && k > 0) {
        fast = fast.next
        k--
    }
    while (fast) {
        fast = fast.next
        slow = slow.next
    }
    return slow;
};

知识点

这一次我又学习到了一个新的方法：快慢指针

快慢指针：是指将第一个指针 fast 指向链表的第 k+1 个节点，第二个指针 slow 指向链表的第一个节点，此时指针 fast 与 slow 二者之间刚好间隔 k 个节点。此时两个指针同步向后走，当第一个指针 fast 走到链表的尾部空节点时，则此时 slow 指针刚好指向链表的倒数第k个节点。