十分钟教你学会快慢指针法
字节逆旅
共 2712字，需浏览 6分钟
·
2021-06-26 20:59
题目描述
输入一个链表，输出该链表中倒数第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)，变量都是常量阶的;
参考链接:
https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/solution/jskuai-man-zhi-zhen-by-liberhome-dnxt/ https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
评论