【数据结构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的内容能够距离边缘有一定的间隙,确保内容显示完整。这…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
