当前位置: 首页 > news >正文

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&#xf…...

hibernate学习(五)

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

STM32CubeIDE 快速开发入门指南

描述 STM32CubeIDE是一体式多操作系统开发工具,是STM32Cube软件生态系统的一部分。 STM32CubeIDE是一种高级C/C开发平台,具有STM32微控制器和微处理器的外设配置、代码生成、代码编译和调试功能。它基于Eclipse/CDT™框架和用于开发的GCC工具链&#xf…...

华为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五个系统&#xff…...

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 摘要 癫痫发作预测作为慢性脑疾病中最具挑战性的数据分析任务之一,引起了众多研究者的广泛关注。癫痫发作预测,可以在许多方面大大提高患者的生活质量&#xff0…...

【计算机网络】Tcp IP 面试题相关

互联网协议群(TCP/IP):多路复用是怎么回事? 1.【问题】IPv4 和 IPv6 有什么区别? IPv4 是用 32 位描述 IP 地址,理论极限约在 40 亿 IP 地址; IPv6 是用 128 位描述 IP 地址,IPv6 可…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...

龙虎榜——20250610

上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

【AI学习】三、AI算法中的向量

在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则&#xf…...