LeetCode - 02.02.返回倒数第 k 个节点
目录
题目
解法一
双指针算法
原理
详细过程
为什么它有效?
时间复杂度与空间复杂度
代码
解法二
递归算法
核心思想
执行流程详解
具体例子
代码
题目
面试题 02.02. 返回倒数第 k 个节点 - 力扣(LeetCode)
解法一
双指针算法
原理
- 设置距离:快慢指针之间维持k个节点的固定距离
- 同步移动:当快指针到达链表末尾时,慢指针恰好指向倒数第k个节点
详细过程
初始化:两个指针fast和slow都指向链表头节点
head -> 1 -> 2 -> 3 -> 4 -> 5 -> NULLfast^slow^
建立间距:让fast指针先走k步,建立k个节点的距离
例如,k=2,fast先走2步head -> 1 -> 2 -> 3 -> 4 -> 5 -> NULLfast^slow^
同步移动:然后fast和slow同时向前移动,保持k个节点的距离
第一步同时移动:head -> 1 -> 2 -> 3 -> 4 -> 5 -> NULLfast^slow^第二步同时移动:head -> 1 -> 2 -> 3 -> 4 -> 5 -> NULLfast^slow^第三步同时移动:head -> 1 -> 2 -> 3 -> 4 -> 5 -> NULLfast^slow^
找到结果:当fast指针到达NULL(链表末尾)时,slow指针恰好指向倒数第k个节点
head -> 1 -> 2 -> 3 -> 4 -> 5 -> NULLfast^ (已经是NULL)slow^ (这就是倒数第2个节点)
为什么它有效?
这个方法之所以有效,是因为:
- 如果链表长度为n,倒数第k个节点就是正数第(n-k+1)个节点
- 当fast指针先走了k步,然后两个指针一起走,直到fast到达NULL(即走了n步)
- 此时slow指针走了(n-k)步,所以它指向的是第(n-k+1)个节点,即倒数第k个节点
时间复杂度与空间复杂度
- 一次遍历:只需要遍历链表一次,时间复杂度O(n)
- 常数空间:只使用两个指针,空间复杂度O(1)
- 无需知道链表长度:不需要预先计算链表的长度
代码
class Solution {
public:int kthToLast(ListNode* head, int k) {ListNode* fast = head;ListNode* slow = head;for(int i = 0;i < k;i++){head = head->next;fast = head;}while(fast != nullptr){fast = fast->next;slow = slow->next;}return slow->val;}
};
解法二
递归算法
核心思想
这种递归方法使用"后序遍历"的思想 - 先递归到链表末尾,然后在回溯过程中进行计数,找到倒数第 k 个节点。
执行流程详解
- 递进阶段:
- 递归函数 dfs 首先检查当前节点是否为空
- 如果不为空,继续递归调用自己,传入下一个节点:dfs(head->next, k)
- 这个过程会一直进行,直到到达链表的末尾(遇到 nullptr)
- 回溯阶段:
- 当到达链表末尾时,开始回溯
- 每次回溯一层,计数器 count 加1
- 当计数器等于指定的 k 值时,当前节点就是倒数第 k 个节点
- 将这个节点的值保存到 ret 中
具体例子
假设链表为 1->2->3->4->5,k=2(寻找倒数第2个节点):
初始调用: kthToLast(head, 2)
- 调用 dfs(head, 2),此时 count 为 0
递归调用展开:
dfs(1) -> dfs(2) -> dfs(3) -> dfs(4) -> dfs(5) -> dfs(nullptr)
回溯过程:
- dfs(nullptr) 检测到空节点,直接返回
- 回到 dfs(5):count++ 变为 1,1≠2,继续回溯
- 回到 dfs(4):count++ 变为 2,2=2,设置 ret = 4
- 回到 dfs(3):count++ 变为 3,3≠2,继续回溯
- 回到 dfs(2):count++ 变为 4,4≠2,继续回溯
- 回到 dfs(1):count++ 变为 5,5≠2,继续回溯
- 所有递归调用结束,ret 的值为 4
返回结果: kthToLast 返回 ret 的值,即 4
代码
class Solution {int ret;int count;
public:int kthToLast(ListNode* head, int k) {dfs(head,k);return ret;}void dfs(ListNode* head, int k){if(head==nullptr){return;}dfs(head->next,k);count++;if(k == count){ret = head->val;}}
};
相关文章:
LeetCode - 02.02.返回倒数第 k 个节点
目录 题目 解法一 双指针算法 原理 详细过程 为什么它有效? 时间复杂度与空间复杂度 代码 解法二 递归算法 核心思想 执行流程详解 具体例子 代码 题目 面试题 02.02. 返回倒数第 k 个节点 - 力扣(LeetCode) 解法一 双指针算…...
<c++>使用detectMultiScale的时候出现opencv.dll冲突
最近在试着弄一下opencv,看网上很多人都是的用的python,但是python跑起来没有c快,生成的qt工程也大一些,想着试试c看能不能生成opencv。然后就用到这个函数,detectMultiScale。 出现一个问题,就是我的程序在…...
从实列中学习linux shell脚本2: shell 的变量 方法 命名和使用规则之类 比如拿:获取cpu 负载,以及负载超过2.0 以后就发生邮件为例子
以下是对 Linux Shell 中变量、方法(函数)、命名规则的详细说明,并结合 获取CPU负载并在负载超过2.0时发送邮件 的示例进行演示: 1. Shell 变量 命名规则 命名格式:变量名由字母、数字、下划线组成,不能以…...
Centos Ubuntu RedOS系统类型下查看系统信息
文章目录 一、项目背景二、页面三、说明四、代码1.SysInfo2.EmsSysConfig3.HostInformationController4.HostInfo 一、项目背景 公司项目想展示当前部署系统的:操作系统,软件版本、IP、主机名。 二、页面 三、说明 说明点1:查询系统类型及…...
【Hive入门】Hive高级特性:视图与物化视图
在大数据分析中,Hive作为Hadoop生态系统中的重要组件,提供了强大的数据查询和管理能力。除了基本表的操作,Hive还支持 视图和 物化视图,这两种特性在数据管理和查询优化中扮演着重要角色。本文将深入探讨视图的创建与性能影响&…...
特征工程四-2:使用GridSearchCV 进行超参数网格搜索(Hyperparameter Tuning)的用途
1. GridSearchCV 的作用 GridSearchCV(网格搜索交叉验证)用于: 自动搜索 给定参数范围内的最佳超参数组合。交叉验证评估 每个参数组合的性能,避免过拟合。返回最佳模型,可直接用于预测或分析。 2. 代码逐行解析 (1…...
【Hive入门】Hive函数:内置函数与UDF开发
Apache Hive作为Hadoop生态系统中的重要组件,为大数据分析提供了强大的SQL-like查询能力。Hive不仅支持丰富的内置函数,还允许用户开发自定义函数(UDF)以满足特定需求。本文将深入探讨Hive的内置函数(包括数学函数、字…...
HTML Picture标签详细教程
HTML Picture标签详细教程 简介 <picture>标签是HTML5中引入的一个强大元素,它为开发者提供了更灵活的图像资源管理方式。该标签主要用于让浏览器根据不同条件(如设备屏幕大小、分辨率或支持的图像格式)选择最适合当前显示环境的图像…...
Html1
一,HTML概述 网页开发需要学习的知识: html css javaScript 两个框架 VUE.js ElementUI UI user interface 用户界面 HTML xml 可扩展标记语言-->存储数据 Markup Language标签语言都会提供各种标…...
runpod team 怎么设置自己的ssh key呢?
生成 ed25519 公钥密钥 ssh-keygen -t ed25519 -C "yourqq.com"然后在pod容器配置key以及启动方式 选择edit pod 添加启动代码 启动代码可以参考官方给的内容: https://docs.runpod.io/pods/configuration/use-ssh bash -c apt update;DEBIAN_FRONT…...
Flutter:组件10、倒计时
import dart:async; import package:flutter/material.dart;class CountdownTimer extends StatefulWidget {final int seconds;final double? fontSize;final Color? textColor;final bool showDays;final bool showHours;final bool showMinutes;final bool showSeconds;fi…...
存储器分类
按宏观分类 内部存储:用于临时存储当前程序运行所需要的数据外部存储:指硬盘,用于存储需要保存下的数据 按存储功能分 磁盘存储器(Disk),如机械硬盘非易失性存储器(Flash memory),分为固态硬…...
案例解析:基于量子计算的分子对接-QDOCK(Quantum Docking)
分子对接(Moleculardocking)在药物发现中具有重要意义,但对接的计算速度和准确率始终难以平衡,其巨大解搜索空间对传统计算机来说异常艰巨。 本文通过引入网格点匹配(GPM, Grind point matching)和特征原子…...
人工智能和机器学习在包装仿真中的应用与价值
引言 随着包装成为消费品关键的差异化因素,对智能设计、可持续性和高性能的要求比以往任何时候都更高 。为了满足这些复杂的期望,公司越来越多地采用先进的仿真方法,而现在人工智能 (AI) 和机器学习 (ML) 又极大地增强了这些方法 。本文探讨…...
系统的环境变量
目录 基本概念 用途之一 环境变量表 命令行参数表 理解 更多的环境变量 基本概念 环境变量(environmentvariables)⼀般是指在操作系统中⽤来指定操作系统运⾏环境的⼀些参数。环境变量通常具有某些特殊⽤途,还有在系统当中通常具有全局特性 用途之一 我们看…...
css3伸缩盒模型第一章(主轴以及伸缩盒模型)
css3伸缩盒模型第一章(主轴) 一、伸缩盒模型简介 2009 年, W3C 提出了一种新的盒子模型 —— Flexible Box (伸缩盒模型,又称:弹性盒 子)。它可以轻松的控制:元素分布方式、元素对齐方式、元素视觉顺序 ……...
【MySQL】(9) 视图
一、什么是视图 视图是一张虚拟表,是表、其它视图的查询结果集。它本身不像基础表(物理表)一样存储数据,而是将 SQL 查询语句包装起来,通过执行查询语句动态生成数据。 二、视图的作用 当我们需要频繁使用一条查询语句…...
day10 python机器学习全流程实践
在机器学习的实践中,数据预处理与模型构建是极为关键的环节。本文将回顾数据预处理的全流程,并基于处理后的数据完成简单的机器学习建模与评估,暂不涉及复杂的调参过程。 一、预处理流程回顾 机器学习的成功,很大程度上依赖于高…...
Rust Ubuntu下编译生成环境win程序踩坑指南
前言: 1,公司要给一线搞一个升级程序,需要在win下跑。 之前都是找开发总监帮忙,但是他最近比较忙。就让我自己搞。有了下文.。说来惭愧,之前写过一篇ubuntu下编译windows的文章。里面的demo就一句话 fuck world。依赖…...
2025年- H12-Lc119-56.合并区间(普通数组)---java版
1.题目描述 2.思路 思路参考了代码随想录: 按照左边界从小到大排序之后,如果 intervals[i][0] < intervals[i - 1][1] 即intervals[i]的左边界 < intervals[i - 1]的右边界,则一定有重叠。(本题相邻区间也算重贴ÿ…...
合并两个有序链表
题目:21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 [1,2,4], l2 [1,3,4] 输出:[1,1,2,3,4,4]示例 2: 输入&#x…...
rsync命令详解与实用案例
rsync命令详解与实用案例 rsync是一款功能强大的Linux文件同步工具,通过高效的增量传输算法,能够显著减少数据传输量和时间,是备份、镜像和跨平台文件同步的理想选择。其核心价值在于只传输文件的差异部分,而非全量复制ÿ…...
gitee 如何修改提交代码的邮箱
gitee 如何修改提交代码的邮箱 1. 修改全局提交邮箱2. 修改特定仓库的提交邮箱3. 修改已提交记录的邮箱 4. 可能遇到的问题git filter-repo 拒绝执行解决办法方法一:使用 --force 参数 (亲测有效)方法二:创建一个全新的克隆仓库 注…...
MATLAB画一把伞
% 伞的参数num_ribs 5; % 伞骨数量修改为5R 1; % 伞的半径height 0.5; % 伞的高度handle_length 2; % 伞柄长度semicircle_radius 0.26; % 伞柄末端半圆的半径% 生成伞叶网格theta linspace(0, 2*pi, 100);phi linspace(0, pi/2, 50);[Theta, Phi] meshgrid(theta, phi…...
vue 实现文件流下载功能 前端实现文件流下载
首先场景就是,一般的文件下载是通过后端返回的文件地址下载文件,但当后端返回的是文件流的时候,下载要做特殊处理 案例截图: 下载成功: 代码处理,首先就是要在接口封装的地方加上 在 Vue 前端开发中实现文件流下载与普通文件下载的核心区别在于 数据处理方式。文件流…...
[Android]导航栏中插入电源菜单
1. 新增 frameworks/base/packages/SystemUI/res/layout/power.xml <?xml version"1.0" encoding"utf-8"?> <com.android.systemui.navigationbar.buttons.KeyButtonView xmlns:android"http://schemas.android.com/apk/res/android"…...
VSCode Verilog环境搭建
VSCode Verilog环境搭建 下载Iverilog安装Iverilog验证安装VS Code安装插件 下载Iverilog 官网下载Iverilog 安装Iverilog 一定要勾选这两项 建议勾选这两项 验证安装 运行Windows PowerShell输入命令:iverilog输入命令:Get-Command gtkwave …...
Hadoop 和 Spark 生态系统中的核心组件
通过jps命令,可以看到如下进程名,请解释一下它们各自是哪个命令产生的,有什么作用?一、Worker 1.来源:Spark 集群的 工作节点(Worker Node),由 start-worker.sh 启动 2.作用&#…...
MySQL多表操作
熟能生巧,全部代码在最后!!! 一、多表关系 一对一关系、一对多关系、多对多关系 注意多对多关系必须有中间表进行关联 多对多的关系就相当于是两个一对多关系 二、创建外键约束 专门用于多表操作的一种约束方式 控制的那个表…...
WPF TextBlock控件性能优化指南
WPF TextBlock控件性能优化指南 1. 引言 TextBlock作为WPF中最基础且使用最广泛的文本显示控件,其性能优化对整个应用程序的响应速度和资源占用有着重要影响。尽管TextBlock是一个轻量级控件,但在大型应用或需要显示大量文本的场景中,不恰当…...
DotNet 入门:(一) 环境安装
一、前言 本想用 Go 语言实现一个通过小爱同学操作电脑的,比如我对着手机说打开音乐,或调小音乐,电脑能做相应的处理。奈何我一时间没看懂,就想着用.Net 来试一下,于是就有了下面这篇文章。 二、安装.Net 环境 1. 下…...
初识Redis · 分布式锁
目录 前言: 分布式锁 setnx lua脚本和看门狗 redlock算法 Redlock 的加锁流程(5 步) 前言: 到了分布式锁这一章之后,我们首先能联想到的问题就是线程安全的问题,线程安全指的是多个线程在并发执行的…...
使用 OpenCV 实现图像中心旋转
在图像处理中,围绕中心点旋转图像是一个常见的需求。无论是为了数据增强、视觉效果,还是图像对齐,旋转图像都是一项基础且重要的操作。本文将详细介绍如何使用 OpenCV 实现围绕图像中心旋转的功能,并深入探讨其背后的数学原理。 一…...
云钥科技红外短波工业相机
云钥科技的红外短波相机是一款基于短波红外(SWIR,波长范围约1-3微米)技术的成像设备,专为高精度检测、全天候成像及特殊场景应用设计。以下从核心技术、性能参数、应用场景及产品优势等方面进行详细介绍: 一、核心…...
npm如何安装pnpm
在 npm 中安装 pnpm 非常简单,你可以通过以下步骤完成: 1. 使用 npm 全局安装 pnpm 打开终端(命令行工具),运行以下命令: npm install -g pnpm2. 验证安装 安装完成后,可以检查 pnpm 的版本以确保安装成功: pnpm --version如果正确显示版本号(如 8.x.x),说明安…...
GTC Taipei 2025 医疗域前瞻:从AI代理到主权生态,解码医疗健康与生命科学的未来图景
引言 2025年,全球医疗健康领域正经历一场由人工智能、机器人技术与分布式计算驱动的范式转移。随着NVIDIA及其生态伙伴在GTC Taipei 2025大会上的深度布局,医疗行业的核心趋势愈发清晰:AI代理程序(Digital AI Agents)赋能临床协作、医疗大数据与精准医学加速落地、医学影…...
【AI学习】李宏毅新课《DeepSeek-R1 这类大语言模型是如何进行「深度思考」(Reasoning)的?》的部分纪要
针对推理模型,主要讲了四种方法,两种不需要训练模型,两种需要。 对于reason和inference,这两个词有不同的含义! 推理时计算不是新鲜事,AlphaGo就是如此。 这张图片说明了将训练和推理时计算综合考虑的关系&…...
npm打包内存不足- JavaScript heap out of memory
直接贴出报错信息 <--- Last few GCs --->[30904:0000010F60FE58E0] 22090 ms: Scavenge 2037.4 (2069.4) -> 2036.4 (2074.2) MB, 2.5 / 0.0 ms (average mu 0.228, current mu 0.216) allocation failure [30904:0000010F60FE58E0] 22101 ms: Scavenge 2…...
【最新 MCP 战神手册 08】工具使用详解:实现 AI 行动
文章目录 1. 开始啦!2. 第一部分:设计高效且安全的工具3. 第二部分:定义工具蓝图——参数、输出与约束条件4. 第三部分:弥合差距:LLM 兼容性(函数调用)5. 第四部分:实施与测试的最佳实践1. 开始啦! 在前几章中,我们将工具介绍为 AI 模型在 MCP 客户端引导下向 MCP 服…...
开发iOS App时,我常用的一款性能监控小工具分享
开发iOS App时,我常用的一款性能监控小工具分享 最近在做一个iOS应用的性能优化,频繁遇到内存泄露、界面卡顿和网络请求超时的问题。平时用Xcode Instruments虽然专业,但流程繁琐,临时排查问题不够灵活。 于是开始找有没有轻量一…...
如何防止 ES 被 Linux OOM Killer 杀掉
当 Linux 系统内存不足时,内核会找出一个进程 kill 掉它释放内存,旨在保障整个系统不至于崩溃。如果 ES 按照最佳实践去实施部署,会保留一半的内存,不至于发生此类事情。但事情总有例外,有的朋友可能 ES 和其他的程序部…...
Windows权限与icacls命令详解
在Windows操作系统中,权限管理是确保系统安全和资源访问控制的核心机制。特别是在使用NTFS(New Technology File System)文件系统的环境中,访问控制列表(ACL)用于定义哪些用户或组可以对文件、文件夹或其他…...
5.4.2 MVVM例2-用户控件的使用(水在水管中流动的实例)
本文以一个例子介绍用户控件的使用(UserControl),下图所示: 一、主要技术点 1.MainViewModel使用CommunityToolkit.Mvvm 这个Nuget包 2.LinearGradientBrush使用,下面代码可以产生如下的效果 <LinearGradientBrush x:Key="HorizontalBackground" …...
PHP代码-服务器下载文件页面编写
内部环境的服务资源下载页面有访问需求,给开发和产品人员编写一个简洁的下载页面提供资源下载。直接用nginxphp的形式去编写了,这里提供展示index.php文件代码如下: <?php // 配置常量 define(BASE_DIR, __DIR__); // 当前脚本所在目录作…...
51单片机快速入门之 SPI通信 2025年4月29日09:26:32
SPI通信 : SPI(Serial Peripheral Interface)通信是一种同步串行数据传输协议,主要用于嵌入式系统内部设备之间的通信。它由Motorola公司在2000年提出,广泛应用于微控制器、传感器、存储设备等之间的数据传输。 SPI通信的主要特点…...
SpringMVC再复习1
一、三层架构 表现层(WEB 层) 定义 :是应用程序与客户端进行交互的最外层,主要负责接收用户的请求,并将处理结果显示给用户。 作用 :在 Spring MVC 中,表现层通常采用 MVC 设计模式来构建。 技…...
音视频之H.265/HEVC网络适配层
H.265/HEVC系列文章: 1、音视频之H.265/HEVC编码框架及编码视频格式 2、音视频之H.265码流分析及解析 3、音视频之H.265/HEVC预测编码 4、音视频之H.265/HEVC变换编码 5、音视频之H.265/HEVC量化 6、音视频之H.265/HEVC环路后处理 7、音视频之H.265/HEVC熵编…...
01_微服务常见问题
文章目录 微服务常见问题一、常见问题概要一、问题详解1.1 服务拆分1.2 服务通信1.3 服务注册与发现1.4 服务治理1.5 数据一致性1.6 故障隔离与容错处理1.7 数据库设计1.8 性能测试与调优 微服务常见问题 一、常见问题概要 服务拆分:如何合理地拆分服务&#…...
Python在自动驾驶仿真环境中的应用:构建智能驾驶的虚拟世界
Python在自动驾驶仿真环境中的应用:构建智能驾驶的虚拟世界 引言 随着自动驾驶技术的迅速发展,仿真环境的构建变得愈发重要。传统的测试方法依赖物理车辆和道路进行验证,但这种方式不仅成本高昂,还存在一定的风险。为了加速自动驾驶技术的研发,仿真环境成为了一个必不可…...
【统计方法】交叉验证:Resampling, nested 交叉验证等策略 【含R语言】
Resampling (重采样方法) 重采样方法是从训练数据中反复抽取样本,并在每个(重新)样本上重新调整模型,以获得关于拟合模型的附加信息的技术。 两种主要的重采样方法 Cross-Validation (CV) 交叉验证 : 用于估计测试误…...