专栏首页YuanXin剑指offer - 链表中倒数第k个结点 - JavaScript

剑指offer - 链表中倒数第k个结点 - JavaScript

题目描述:输入一个链表,输出该链表中倒数第 k 个结点。

题目描述

输入一个链表,输出该链表中倒数第 k 个结点。

解法 1: 两次循环

因为要求链表倒数第 k 个节点,也就是求正数第length - k个节点。整体过程如下:

  • 链表又是个单链表,并且没有保存长度信息。所以需要循环一次计算length
  • 第二次循环找到第length - k个节点。

时间复杂度是 O(N),需要 2 次循环。

代码如下:

// ac地址:https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
// 原文地址:https://xxoo521.com/2020-01-11-dao-shu-topk/
/**
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let length = 0;
    let node = head;
    while (node) {
        ++length;
        node = node.next;
    }

    if (k > length) {
        return null;
    }

    node = head;
    let offset = length - k;
    for (let i = 0; i < offset; ++i) {
        node = node.next;
    }
    return node;
};

解法 2: 快慢(双)指针

准备两个指针:left(慢)和 right(快)。整体过程如下:

  • right 先向右移动 k 位,此时 index(right) - index(left) = k
  • left 和 right 一起向右移动,直到 right 抵达边界
  • 由于index(right) - index(left) = k,所以index(left) = index(right) - k = length - k。也就是 left 指针移动到了倒数第 k 个位置

时间复杂度是 O(N),但仅需要遍历一次。空间复杂度是 O(1)

代码如下:

// ac地址:https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
// 原文地址:https://xxoo521.com/2020-01-11-dao-shu-topk/
/**
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let right = head;
    for (let i = 0; i < k; ++i) {
        if (right === null) {
            // 链表长度小于k
            return null;
        }
        right = right.next;
    }

    let left = head;
    while (right) {
        left = left.next;
        right = right.next;
    }

    return left;
};

相关题目

更多资料

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【剑指offer:两个链表的第一个公共节点】双解法

    题目提示了,空间复杂度可以降低到$O(1)$。这时候不能用哈希表,可以使用快慢指针的思路来处理。整体思路如下:

    心谭博客
  • 【剑指offer:和为s的两个数字】双指针

    题目描述:输入一个递增排序的数组和一个数字 s,在数组中查找两个数,使得它们的和正好是 s。如果有多对数字的和等于 s,则输出任意一对即可。

    心谭博客
  • 设计模式 - 单例模式 - JavaScript

    如果一个类负责连接数据库的线程池、日志记录逻辑等等,此时需要单例模式来保证对象不被重复创建,以达到降低开销的目的。

    心谭博客
  • 随机森林基本原理

    基础内容: 这里只是准备简单谈谈基础的内容,主要参考一下别人的文章,对于随机森林与GBDT,有两个地方比较重要,首先是information gain,其次是决...

    学到老
  • Scala教程之:PartialFunction

    Scala中有一个很有用的traits叫PartialFunction,我看了下别人的翻译叫做偏函数,但是我觉得部分函数更加确切。

    程序那些事
  • Tomcat在idea中乱码

    我们在idea中刚开始运行Tomcat时,会发现日志打印出来的是乱码的,这个问题理论上不需要去理会,我们一般都不去看,但是也有人会受不了,那么我们就去修改一下这...

    乐心湖
  • pandas文本处理

    py3study
  • 从ClickHouse的名字由来讲起

    <ClickHouse原理解析和开发实战>,可以说2019年的绝大部分深夜,都与写作共度春宵了。现在写作临近尾声,终于有时间来扯些闲篇了。

    Nauu
  • ClickHouse为何如此之快?

    作为一个拥有ClickHouse信仰标签的忠实粉丝,我自然也是追寻谜底的一份子。在我苦苦寻觅许久之后,今天,终于被我找到了答案。所以特地拿来与各位分享,谜底就在...

    Nauu
  • 机器学习集成算法——袋装法和随机森林

    随机森林是最流行、最强大的机器学习算法之一。它是机器学习集成算法中的一种,可称之为自助集成(Bootstrap Aggregation)或袋装法(Bagging...

    人工智能资讯小编

扫码关注云+社区

领取腾讯云代金券