十分钟分析快慢指针法

题目描述

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

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

示例：

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

返回链表 4->5.
复制代码

题目分析

这是个链表题目，先一句句分析(其实第一句就已经是完整的题目了)，要输出链表中倒数第k个节点。其实很容易想到遍历，最后取倒数第k个就可以了，前提是你得知道链表的长度。事实上，链表的长度并不知道，需要你自己算出来。
所以我们考虑下有没有更好的办法，这里推荐快慢指针法。

快慢指针法

如图所示，这里遍历链表时，给两个指针，一个快，一个慢，中间相差k个节点，等快的那个走到最后了，慢的那个就是要的结果了。思路是不是很清晰？！

没接触过链表的可以先看这段代码体会下链表节点的构造：

function ListNode(val) {
    this.val = val;
    this.next = null;
 }
复制代码

下面是题解

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    var former = head,latter = head;
    for(var i =0;i<k;i++){
        former = former.next;
    }
    while(former!=null){
        former = former.next;
        latter = latter.next;
    }
    return latter
};
复制代码

其中former代表的是快指针，latter是慢指针，它们的起点相同，都是从链表头部head开始，former先走了k个节点，然后慢指针latter才开始启动，与快指针former同步往后走，这个差距始终都是k个节点。最终，当former走完最后节点，变成null时，latter就是此完整链表的倒数第k个节点了。

这里还有另一种表达方式，也可以参考，意思是一样的。

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let fast = head;
    let slow = head;
    let flag = 0;
    while (fast) {
        if (flag >= k) {
            slow = slow.next;
        }
        fast = fast.next;
        flag ++;
    }
    return slow;
};
复制代码

复杂度分析

时间复杂度都是O(n),n为链表长度；空间复杂度都是O(1)，变量都是常量阶的;

参考链接:

1. leetcode-cn.com/problems/li…
2. leetcode-cn.com/problems/li…