Leetcode 141.环形链表 142环形链表II
141环形链表
文章目录
- 快慢指针
快慢指针
代码思路:
slow 和fast 指向 head slow走一步,fast走两步
没有环:
fast每次走2步 ,如果 fast 最终遇到NULL(链表中的元素是 偶数)或者fast->next(链表中的元素是 奇数)遇到NULL,说明链表中没有环
有环:
如果 fast 和 slow指针在途中相遇 ,说明这个链表有环
因为fast 比slow 走的快 , 如果 fast 最终和 slow 相遇,那肯定是 fast 超过了 slow 一圈,说明链表中含有环。
bool hasCycle(struct ListNode *head){struct ListNode * slow =head , * fast = head ;//假设带环while ( fast!= NULL && fast->next != NULL){ fast =fast->next->next ;slow = slow->next ;if( slow == fast ) //因为fast每次走2步 ,slow每次走一步 如果有环 那一定是fast追上slow 也就是相遇{return true ;}}//fast 为NULL 或者 fast->next 为NULL 如果 fast 最终遇到空指针,说明链表中没有环 return false ;
}
我们证明一下这个逻辑问题:
为什么 slow 走一步 fast 走两步 ,fast 和slow 会相遇 ,有没有可能会错过
假设slow 刚开始进环的时候 slow 和fast 的距离是N ,slow开始进环的时候 fast开始追及slow ,因为fast 每次走两步 ,而slow 每次走一步 ,也就是说在追及的过程中 fast 与slow每次缩短一步的距离
不管N 是否为奇数还是偶数 , N每次减一 ,迟早为0 ,也就意味着fast 追上了 slow
那我们再推广一下
如果slow 走一步 ,fast 走 X 步( X >=3) ,fast 和slow 会相遇 ? 或者有可能错过?
假设slow刚开始进环 ,fast 和slow 的距离是N
slow进环以后 fast 开始追及slow ,slow每次走一步 ,fast 就走三步 ,距离缩小 2 步
如果N 是偶数 N -2 , N-4 , N - 6 , 4 , 2 …N可以减到零
如果N 是奇数 N -2 , N-4 , … 3 ,1, -1
我们假设环的周长是C ,N 是 -1 , 也就是说 fast 和slow 的距离变成了 C-1 ,又开始了新的一轮追及
142.环形链表II
结论 : 一个指针(fast)从相遇点开始走 ,一个指针(slow)从起始点开始走 ,会在入口点相遇
结论千万不要理解为slow 去追fast 了 ,其实是fast追slow ,只不过fast走的快 ,可能在环里转了n 圈
一旦slow走到入口点 ,fast 就会和slow 相遇
下面我们来证明一下上述结论:
假设起始点到入口点处的距离是L , 入口点处到相遇点的距离为X
环的长度为C
那么可以推出slow 走的距离为L + X ,
fast 走的距离是 L+ n* C + X ,
n* C 表示 slow 进环前 ,fast 在环里转了n*C 圈
根据fast 走的距离 是slow 的两倍
2(L+X ) = L + n *C + X
推出 L= n * C -X
将这个推导式变形 得到 L = ( n -1) * C + C -X
即证明结论成立
struct ListNode *detectCycle(struct ListNode *head){struct ListNode * fast = head , * slow = head ;// 假设带环while ( fast != NULL && fast->next!=NULL){slow =slow->next ;fast =fast->next->next ;if( slow == fast ) {struct ListNode * meet = fast ; //相遇点struct ListNode * start = head ;//起始点while( meet!= start ) // 一个指针(fast)从相遇点开始走 ,一个指针(slow)从起始点开始走 ,会在入口点相遇{meet= meet->next ;start=start->next ;}return meet ;}}return NULL ; //不带环}
如果你觉得这篇文章对你有帮助,不妨动动手指给点赞收藏加转发,给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力!!!
相关文章:

Leetcode 141.环形链表 142环形链表II
141环形链表 文章目录快慢指针快慢指针 代码思路: slow 和fast 指向 head slow走一步,fast走两步 没有环: fast每次走2步 ,如果 fast 最终遇到NULL(链表中的元素是 偶数)或者fast->next(链表中的元素是 奇数)遇到NULL…...

hibernate学习(五)
hibernate学习(五) hibernate的一对多关联映射: 一、数据库表与表之间关系 一对多建表原则: 多对多的建表原则: 一对一建表原则: (1)唯一外键对应: (…...

STM32CubeIDE 快速开发入门指南
描述 STM32CubeIDE是一体式多操作系统开发工具,是STM32Cube软件生态系统的一部分。 STM32CubeIDE是一种高级C/C开发平台,具有STM32微控制器和微处理器的外设配置、代码生成、代码编译和调试功能。它基于Eclipse/CDT™框架和用于开发的GCC工具链…...
华为OD机试 - 火星文计算(C 语言解题)【独家】
最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧文章目录 使用说明本期题目:火星文计…...

超超超超保姆式详解——字符函数和字符串函数(学不会打我)上
目录 长度不受限制的字符串函数 strlen部分 strlen函数的易错小知识 strlen函数的实现 strcpy部分 strcat部分 自己实现strcat strstr函数部分 简单例子: 分析 strcmp部分 长度受限制的字符串函数 strncpy 简单例子 strncat strncmp 简单例子 &…...
Data mesh 笔记
有用的网站 https://www.datamesh-architecture.com/ https://www.agilelab.it/data-mesh-in-action https://learn.microsoft.com/en-us/azure/cloud-adoption-framework/scenarios/cloud-scale-analytics/well-architected-framework https://www.datamesh-architecture.com…...
(八十三)大白话透彻研究通过explain命令得到的SQL执行计划(2)
今天我们就一步一步的来讲解不同的SQL语句的执行计划长什么样子,先来看第一条SQL语句,特别的简单,就是: explain select * from t1 就这么一个简单的SQL语句,那么假设他这个里面有大概几千条数据,此时执行计…...

案例18-面向对象之开门小例子
目录 一:背景介绍 二:思路&方案 1.面向过程 2.面向对象 3.面向对象(反射) 三:过程 1.面向过程:原本何老师的作用交给我了米老师来完成。 2.面向对象:把开门的方法完全交个何老师,米老师不需要有…...

【碎片化知识总结】三月第一周
目录 前言 1、开发中常用的 IDEA 编辑器,如何做到不用每次都重新配置? 2、如何使用 Python 获取视频文件信息? 3、使用 Java 的 try-with-resources 优化代码 4、使用 shell 脚本批量修改服务器某一目录下的文件后缀名称 5、MySQL优化&…...
从零开始的JSON库(1):启程
1. JSON 是什么 JSON(JavaScript Object Notation)是一个用于数据交换的文本格式,现时的标准为ECMA-404 。 虽然 JSON 源自于 JavaScript 语言,但它只是一种数据格式,可用于任何编程语言。现时具有类似功能的格式有X…...

【Java】数组
目录 1.数组的定义与初始化 2.遍历数组 3.认识null 4.引用变量 5.返回多个值 6.数组拷贝 7.数组逆序 8.数组填充 9.小练习 //将整形数组转化为字符串 //二分查找优化 //冒泡排序优化 10.二维数组 //遍历二维数组 //不规则的二维数组 1.数组的定义与初始化 int…...

【C++】非类型的模板参数,特化
目录 1.类型模板参数和非类型模板参数 2.特化 3. 模板的分离编译 4.模板的优缺点 1.类型模板参数和非类型模板参数 之前写模板传的都是类型——类型模板参数 现在想定义两个静态数组,数组长度不同,就可以用模板参数传数值而不是传类型 非类型模板…...

核方法(kernel Method)
核方法 核方法定义 一种能够将在原始数据空间中的非线性数据映射到高维线性可分的方法。 核方法的用处 1、低维数据非线性,当其映射到高维空间(feature space)时,可以用线性方法对数据进行处理。 2、线性学习器相对于非线性学…...

消息队列MQ用来做什么的,市场上主流的四大MQ如何选择?RabbitMQ带你HelloWorld!
文章目录MQ用来做什么的MQ会有什么样的麻烦MQ消息队列模式分类MQ消息队列常用协议市场主流四大MQRabbitMQ项目开发RabbitMQ中的组成部分MQ用来做什么的 省流 :系统解耦、异步调用、流量削峰 系统解耦 首先举例下面这个场景,现有ABCDE五个系统ÿ…...

2023年中国高校计算机大赛-团队程序设计天梯赛(GPLT)上海理工大学校内选拔赛(同步赛) A — E
2023年中国高校计算机大赛-团队程序设计天梯赛(GPLT)上海理工大学校内选拔赛(同步赛) 文章目录A -- A Xor B Problem题目分析codeB -- 吃苹果题目分析codeC -- n皇后问题题目分析codeD -- 分苹果题目分析codeE -- 完型填空题目分析codeA – A…...

一文分析Linux v4l2框架
说明: Kernel版本:4.14 ARM64处理器,Contex-A53,双核 使用工具:Source Insight 3.5, Visio 1. 概述 V4L2(Video for Linux 2):Linux内核中关于视频设备驱动的框架,对上向应用层提供…...

MFC常用控件使用(文本框、编辑框、下拉框、列表控件、树控件)
简介 本文章主要介绍下MFC常用控件的使用,包括静态文本框(Static Text)、编辑框(Edit Control)、下拉框(Combo Box)、列表控件(List Control)、树控件(Tree Control)的使用。 创建项目 我们选择 文件->新建->新建项目,选择MFC程序 选择基于对话…...

13 node 程序后台执行加上 tail 命令, 中断 tail 命令, 同时也中断了 node 程序
前言 呵呵 最近帮朋友解决问题[2022.09.08] 需要启动一个 node 程序, 然后 需要一个 startUp.sh 脚本 然后 反手写了一个过去, 按道理 来说 应该是 后台启动了对应的 node 程序, 然后将 标准输出, 错误输出 输出到 logs/nohup.log 日志文件中, 然后基于 tail 命令 来查看 …...

52癫痫发作预测的有效双自注意力残差网络
Effective dual self-attentional residual networks for epileptic seizure prediction 摘要 癫痫发作预测作为慢性脑疾病中最具挑战性的数据分析任务之一,引起了众多研究者的广泛关注。癫痫发作预测,可以在许多方面大大提高患者的生活质量࿰…...
【计算机网络】Tcp IP 面试题相关
互联网协议群(TCP/IP):多路复用是怎么回事? 1.【问题】IPv4 和 IPv6 有什么区别? IPv4 是用 32 位描述 IP 地址,理论极限约在 40 亿 IP 地址; IPv6 是用 128 位描述 IP 地址,IPv6 可…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...

业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...

大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...

.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...

遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...