【数据结构OJ题】环形链表
原题链接:https://leetcode.cn/problems/linked-list-cycle/description/
目录
1. 题目描述
2. 思路分析
3. 代码实现
1. 题目描述

2. 思路分析
整体思路:定义快慢指针fast,slow,如果链表确实有环,fast指针一定会在环内追上slow指针。
即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行,如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。

我们简化一下这个问题,用一个线段表示前面的不带环部分的链表,用一个圆圈表示带环部分的链表 。

slow一次走1步,fast一次走2步,一定能追上吗?(这里的走的步数可以理解成跳格子)
一定可以追上!
当slow进环以后,fast开始追及slow,假设入环时,它们之间的距离是N。每追及1次,它们之间的距离缩小1。当它们之间的距离为0时,就追上了。

扩展:
slow一次走1步,fast一次走3步,一定能追上吗?
当slow进环以后,fast开始追及slow,假设入环时,它们之间的距离是M。每追及1次,它们之间的距离缩小2。我们假设环的周长是C,这时我们就要分类讨论了:

由此我们可以知道,得看距离M和环的周长C的大小来具体情况具体分析!
那么如果slow一次走1步,fast一次走4步呢?
当slow进环以后,fast开始追及slow,假设入环时,它们之间的距离是K。每追及1次,它们之间的距离缩小3。我们假设环的周长是C,这时我们就要分类讨论了:

由此我们可以知道,得看距离K和环的周长C的大小来具体情况具体分析!
3. 代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode *fast=head,*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(slow==fast)return true;}return false;
}

相关文章:
【数据结构OJ题】环形链表
原题链接:https://leetcode.cn/problems/linked-list-cycle/description/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析 整体思路:定义快慢指针fast,slow,如果链表确实有环,fast指针一定会…...
PySpark-核心编程
2. PySpark——RDD编程入门 文章目录 2. PySpark——RDD编程入门2.1 程序执行入口SparkContext对象2.2 RDD的创建2.2.1 并行化创建2.2.2 获取RDD分区数2.2.3 读取文件创建 2.3 RDD算子2.4 常用Transformation算子2.4.1 map算子2.4.2 flatMap算子2.4.3 reduceByKey算子2.4.4 Wor…...
vue 在IOS移动端中 windon.open 等跳转外部链接后,返回不触发vue生命周期、mounted等相关事件-解决方法
做了一个列表的h5页面,通过点击列表跳转到外部链接,然后返回是回到原来页面状态,类似缓存。发现在ios端返回后,vue 的mounted() 、create()、路由监听等方法都不会执行。在安卓和pc 端都能正常调用。 解决方案:监听pa…...
股票预测和使用LSTM(长期-短期-记忆)的预测
一、说明 准确预测股市走势长期以来一直是投资者和交易员难以实现的目标。虽然多年来出现了无数的策略和模型,但有一种方法最近因其能够捕获历史数据中的复杂模式和依赖关系而获得了显着的关注:长短期记忆(LSTM)。利用深度学习的力…...
Docker搭建个人网盘、私有仓库
1、使用mysql:5.6和 owncloud 镜像,构建一个个人网盘 [rootlocalhost ~]# docker pull mysql:5.6 [rootlocalhost ~]# docker pull owncloud [rootlocalhost ~]# docker run -itd --name mysql --env MYSQL_ROOT_PASSWORD123456 mysql:5.6 [rootlocalhost ~]# doc…...
3种获取OpenStreetMap数据的方法【OSM】
OpenStreetMap 是每个人都可以编辑的世界地图。 这意味着你可以纠正错误、添加新地点,甚至自己为地图做出贡献! 这是一个社区驱动的项目,拥有数百万注册用户。 这是一个社区驱动的项目,旨在在开放许可下向每个人提供所有地理数据。…...
数据处理与统计分析——MySQL与SQL
这里写目录标题 1、初识数据库1.1、什么是数据库1.2、数据库分类1.3、相关概念1.4、MySQL及其安装1.5、基本命令 2、基本命令2.1、操作数据库2.2、数据库的列类型2.3、数据库的字段属性2.4 创建和删除数据库表2.5、数据库存储引擎2.6、修改数据库 3、MySQL数据管理3.1、外键 My…...
OpenCV之特征点匹配
特征点选取 特征点探测方法有goodFeaturesToTrack(),cornerHarris()和SURF()。一般使用goodFeaturesToTrack()就能获得很好的特征点。goodFeaturesToTrack()定义: void goodFeaturesToTrack( InputArray image, OutputArray corners,int maxCorners, double qualit…...
浅谈开关柜绝缘状态检测与故障诊断
贾丽丽 安科瑞电气股份有限公司 上海嘉定 201801 摘要:电力开关柜作为电力系统的关键设备广泛应用于输电配电网络,其运行可靠性直接影响着电力系统供电质量及安全性能。开关柜绝缘状态检测与故障诊断是及时维修、更换和预防绝缘故障的重要技术手段。在阐述开关柜绝…...
Mybatis 动态 SQL
动态 SQL 1. if 标签2. trim 标签3. where 标签4. set 标签5. foreach 标签 1. if 标签 if 标签有很多应用场景, 例如: 在用户进行注册是有些是必填项有些是选填项, 这就会导致前端传入的参数不固定如果还是将参数写死就很难处理, 这时就可以使用 if 标签进行判断 <insert …...
Android studio之 build.gradle配置
在使用Android studio创建项目会出现两个build.gradle: 一. Project项目级别的build.gradle (1)、buildscript{}闭包里是gradle脚本执行所需依赖,分别是对应的maven库和插件。 闭包下包含: 1、repositories闭包 2、d…...
【ElasticSearch】一键安装IK分词器无需其他操作
要注意的时下面命令中的es是我容器的名称,要换成你对应的es容器名 docker exec -it es /bin/bash # 进入容器 ./bin/elasticsearch-plugin install https://github.com/medcl/elasticsearch-analysis- ik/releases/download/v7.12.1/elasticsearch-analysis-ik-7.1…...
在Ubuntu上启动一个简单的用户登录接口服务
一个简单的用户登录接口 我使用 Python 和 Flask 框架来创建这个接口 首先,确保你已经安装了 Python 和 Flask。如果没有安装,可以通过以下命令在 Ubuntu 上安装: sudo apt update sudo apt install python3 python3-pip pip3 install Fla…...
【PHP】函数-作用域可变函数匿名函数闭包常用系统函数
文章目录 函数定义&使用命名规则参数种类默认值引用传递函数返回值return关键字 作用域global关键字静态变量 可变函数匿名函数闭包常用系统函数输出函数时间函数数学函数与函数相关函数 函数 函数:function,是一种语法结构,将实现某一个…...
Python使用pymysql和sqlalchemy访问MySQL的区别
Python使用pymysql和sqlalchemy访问MySQL的区别 1. 两个数据库连接工具的对比 pymysql和sqlalchemy是两个Python中经常用于与MySQL数据库交互的库。都可以连接MySQL数据库,但它们有明显的区别。 (1)特点 pymysql是一个Python模块…...
ubuntu服务器的mysql,更改root密码,并允许远程连接
我只是一个搬运工 更改密码远程连接...
微信小程序【构建npm】使用记录
:: 问题 使用原生微信小程序开发时,通过官方 typescript 模板构建的小程序无法正确执行 构建npm 成功,从而导致我想通过 npm 安装并使用第三方库出现问题 :: 开发环境(可参照) 设备:macOS Ventura 13.0 微信开发者工…...
mybatis入门的环境搭建及快速完成CRUD(增删改查)
又是爱代码的一天 一、MyBatis的介绍 ( 1 ) 背景 MyBatis 的背景可以追溯到 2002 年,当时 Clinton Begin 开发了一个名为 iBATIS 的持久化框架。iBATIS 的目标是简化 JDBC 编程,提供一种更直观、易用的方式来处理数据库操作。 在传统的 JDBC 编程中&…...
《HeadFirst设计模式(第二版)》第九章代码——组合模式
上一章链接: 《HeadFirst设计模式(第二版)》第九章代码——迭代器模式_轩下小酌的博客-CSDN博客 前面说到,当一个菜单里面出现了子菜单的时候,前面的迭代器模式得换成组合模式。 组合模式: 允许将对象组合成树形结构来表现部分-整…...
iOS17 widget Content margin
iOS17小组件有4个新的地方可以放置分别是:Mac桌面、iPad锁屏界面、 iPhone Standby模式、watch的smart stack Transition to content margins iOS17中苹果为widget新增了Content margin, 使widget的内容能够距离边缘有一定的间隙,确保内容显示完整。这…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
什么是VR全景技术
VR全景技术,全称为虚拟现实全景技术,是通过计算机图像模拟生成三维空间中的虚拟世界,使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验,结合图文、3D、音视频等多媒体元素…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
