写点什么

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

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

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


解题思路:


  1. 由于链表没有索引,如果需要查找某个位置的节点,可以先为每个节点做好索引标记,再根据索引查找即可。

  2. 由于数组自带索引,因此只要遍历链表,将每个节点依次 push 到数组中,再按照索引查找。

  3. 虽然使用了数组,比起双指针解法占用了更多空间,假设有多次查询的需求,这样以空间换时间的方式,实际效果也更优。


/**
* 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 arr = []
// 遍历链表,将每个节点保存在数组中
while (head) {
arr.push(head)
head = head.next
}
// 索引arr.length - k即为倒数第k个元素
return arr[arr.length - k]
};
复制代码


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

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

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