程序员面试金典:02.02. 返回倒数第 k 个节点

简介: 程序员面试金典:02.02. 返回倒数第 k 个节点

1. 题目

面试题 02.02. 返回倒数第 k 个节点


2. 描述

实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。


注意:本题相对原题稍作改动


示例:


输入: 1->2->3->4->5 和 k = 2


输出: 4


说明:


给定的 k 保证是有效的。


3. 实现方法

3.1 方法 1

3.1.1 思路

设有两个指针 fast, slow 指向 head;

先将 fast 向后移动 k 次,此时 fast,slow 的距离为 k;

接着同时移动 fast,slow 直到 fast 指向 null;

此时slow.val 即为答案;

3.1.2 实现


public int kthToLast(ListNode head, int k) {
    // 初始化两个指针 fast,slow 指向 head
    ListNode slow = head;
    ListNode fast = head;
    // fast 先向后移动 k 个距离,然后 fast, slow 距离为 k
    for(int i = 0; i < k; i++){
        fast = fast.next;
    }
    // 同时移动 fast,slow 直到 fast 指向 null
    while(fast != null){
        slow = slow.next;
        fast = fast.next;
    }
    return slow.val;
}
目录
相关文章
|
算法 程序员 Go
PHP 程序员学会了 Go 语言就能唬住面试官吗?
【9月更文挑战第8天】学会Go语言可提升PHP程序员的面试印象,但不足以 solely “唬住” 面试官。学习新语言能展现学习能力、拓宽技术视野,并增加就业机会。然而,实际项目经验、深入理解语言特性和综合能力更为关键。全面展示这些方面才能真正提升面试成功率。
141 10
|
JavaScript 前端开发 小程序
CoderGuide 程序员前后端面试题库,打造全网最高质量题库
CoderGuide涵盖范围包括且不限于:前端面试题(Vue,React,JS,HTTP,HTML,CSS面试题等),后端面试题(Java,Python,Golang,PHP,Linux,Mysql面试题等),以及算法面试题,大厂面试题,高频面试题,校招面试题等,你想要的,这里都有!
252 2
|
机器学习/深度学习 算法 数据挖掘
【数据挖掘】 GBDT面试题:其中基分类器CART回归树,节点的分裂标准是什么?与RF的区别?与XGB的区别?
文章讨论了梯度提升决策树(GBDT)中的基分类器CART回归树的节点分裂标准,并比较了GBDT与随机森林(RF)和XGBoost(XGB)的区别,包括集成学习方式、偏差-方差权衡、样本使用、并行性、最终结果融合、数据敏感性以及泛化能力等方面的不同。
258 1
|
JSON NoSQL MongoDB
面试题MySQL问题之想使用Neo4j查询可变数量的关系节点如何解决
面试题MySQL问题之想使用Neo4j查询可变数量的关系节点如何解决
157 1
|
前端开发 应用服务中间件 程序员
老程序员分享:Nginx相关面试题
老程序员分享:Nginx相关面试题
161 2
|
SQL JavaScript Java
java程序员面试题大全含答案(2018--2019)
java程序员面试题大全含答案(2018--2019)
|
存储 Java
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
|
10月前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
|
10月前
|
存储 缓存 算法
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
本文介绍了多线程环境下的几个关键概念,包括时间片、超线程、上下文切换及其影响因素,以及线程调度的两种方式——抢占式调度和协同式调度。文章还讨论了减少上下文切换次数以提高多线程程序效率的方法,如无锁并发编程、使用CAS算法等,并提出了合理的线程数量配置策略,以平衡CPU利用率和线程切换开销。
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
|
10月前
|
存储 缓存 Java
大厂面试必看!Java基本数据类型和包装类的那些坑
本文介绍了Java中的基本数据类型和包装类,包括整数类型、浮点数类型、字符类型和布尔类型。详细讲解了每种类型的特性和应用场景,并探讨了包装类的引入原因、装箱与拆箱机制以及缓存机制。最后总结了面试中常见的相关考点,帮助读者更好地理解和应对面试中的问题。
252 4