写点什么

LeetCode 题解:剑指 Offer 22. 链表中倒数第 k 个节点,双指针,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 11 月 11 日
LeetCode题解:剑指 Offer 22. 链表中倒数第k个节点,双指针,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/



解题思路:



  1. 使用快慢指针,两个指针的距离保持为k。

  2. 当快指针移出链表时,慢指针的位置刚好为链表倒数第k个节点。



/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var getKthFromEnd = function(head, k) {
let slow = head // 慢指针用于存储与快指针距离为k的节点
let fast = head // 快指针用于遍历链表
let distance = 0 // 存储快慢指针的距离
// 遍历链表
while (fast) {
// 当距离不足k时,慢指针不动,快指针移动,每次移动距离+1
if (distance < k) {
distance++
} else {
// 当快慢指针距离为k之后,为保持距离慢指针跟随快指针移动
slow = slow.next
}
// 快指针持续向前移动,当其移出链表时,慢指针的位置即为链表倒数第k个节点
fast = fast.next
}
return slow
};



发布于: 2020 年 11 月 11 日阅读数: 21
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:剑指 Offer 22. 链表中倒数第k个节点,双指针,JavaScript,详细注释