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

链表是否有环、环长度、环起点

问题引入

        如何检测一个链表是否有环,如果有,那么如何确定环的长度及起点。

引自博客:上述问题是一个经典问题,经常会在面试中被问到。我之前在杭州一家网络公司的电话面试中就很不巧的问到,当时是第一次遇到那个问题(毕竟太菜,没有专门准备过算法面试),我思考片刻,问答的是用一个哈希表存储访问的节点的地址,当访问某节点时,发现哈希表中已存在,表明链表中存在环。面试官听了我的回答就反问了我一句:如果链表的环很大,那么哈希表的空间消耗就很大,你的方法并不实用。你能在不消耗额外空间的情况下,找到链表的环吗?当时,想了很久没想到,面试官就说可以这样做,balabala...

算法描述

        解决上述问题的方法就是我们常说的快慢指针。乌龟与兔子在一个含环的跑道上(如图所求)进行比赛,乌龟在单位时间内移动一步,而兔子则在单位时间内移动两步,其移动速度是乌龟的两倍。乌龟与兔子同时从A点出发,兔子移动的快先行进入环形跑道,但那以后,一直在转圈。所以如果存在环的话,乌龟总能与兔子相遇(首次相遇在C点)。

        假设乌龟刚进入环时,兔子在环中任何一位置,此时二者相差距离为m,以后每运动一次兔子两步乌龟一步二者距离减少1,运动几次后距离总能变成0,所以慢指针走一步快指针走两步二者一定能相遇,但慢指针走一步快指针走三步或者其他组合方式可能并不一定能相遇需要注意。

  • 判断是否有环

        定义两个指针p1与p2,起始时,都指向链表的起点A,p1每次移动1个长度,p2每次移动2个长度。如果p2在移到链表的尾端时,并未与p1相遇,表明链表中不存在环。如果p1与p2相遇在环上的某一点C,表明链表有环。

  • 环的长度

        将指针p1固定在相遇位置C,移动p2,每次移动1个长度,并用变量cnt计数。当p2再次与p1相遇时,此时cnt的值就是环的长度。

  • 环的起点

        环的起点即图中点B,将指针p1指向链表的起始位置A,指针p2仍在位置C,指针p1与p2每次均移动一个单位,p1与p2再次相遇的位置就是环的起点位置点B。

简单证明

        上面求链表是否存在环及求环的长度的思路都很好理解,主要是为什么p1与p2再次相遇就是环的起点呢?这里假设从跑道的起始点A到环的起点B的路程为m,从B到相遇点C的路程为k,环的长度为n,相遇时乌龟的爬行路程为S1=m+k+t1*n,兔子的奔跑距离为S2=m+k+t2*n(t2>t1),兔子的速度是乌龟的两倍即S2=2*S1,则S1=S2-S1=(t2-t1)*n,S2=2*(t2-t1)*n,即兔子和乌龟相遇时的奔跑距离都为环的整数倍,而m+k=(t2-2*t1)*n也为环的整数倍。当兔子回到跑道的起始位置,乌龟从相遇点B出发时,这时,两人的速度均为单位时间内爬行1个长度,当兔子到达环的起点B即爬行了m距离时,乌龟则是k+m,此时刚好爬行环的整数倍,也处于环的起点B,即乌龟与兔子再次相遇的位置即为环的起点位置B。

参考链接:弗洛伊德的兔子与乌龟

相关文章:

链表是否有环、环长度、环起点

问题引入 如何检测一个链表是否有环,如果有,那么如何确定环的长度及起点。 引自博客:上述问题是一个经典问题,经常会在面试中被问到。我之前在杭州一家网络公司的电话面试中就很不巧的问到,当时是第一次遇到那个问题&…...

有效文档管理离不开这几个特点

在我们日常生活中经常会遇到各式各样的文档类型,想要把它们都统一管理起来也不是一件容易的事情。后来looklook就去研究怎么样可以把这一堆文档整理起来呢?接下来,looklook就从有效的文档管理展开,和大家分享一下! 有效…...

爬虫-requests-cookie登录古诗文网

一、前言 1、requests简介 requests是一个很实用的Python HTTP客户端库,爬虫和测试服务器响应数据时经常会用到,它是python语言的第三方的库,专门用于发送HTTP请求,使用起来比urllib更简洁也更强大。 2、requests的安装 pip i…...

Spring Boot实践三 --数据库

一,使用JdbcTemplate访问MySQL数据库 1,确认本地已正确安装mysql 按【winr】快捷键打开运行;输入services.msc,点击【确定】;在打开的服务列表中查找mysql服务,如果没有mysql服务,说明本机没有…...

分布式锁漫谈

简单解释一下个人理解的分布式锁以及主要的实现手段。 文章目录 什么是分布式锁常用分布式锁实现 什么是分布式锁 以java应用举例,如果是单应用的情况下,我们通常使用synchronized或者lock进行线程锁,主要为了解决多线程或者高并发场景下的共…...

mac 安装 php 与 hyperf 框架依赖的扩展并启动 gptlink 项目

m系列 mac 安装 php 与 hyperf 框架依赖的扩展并启动 gptlink 项目 gptlink 项目是一个前后端一体化的 chatgpt 开源项目 gptlink 项目地址:https://github.com/gptlink/gptlink 安装 php 8.0 版本: brew install php8.0安装完成后提示如下&#xff…...

ansible中run_once的详细介绍和使用说明

在Ansible中,run_once是一个用于控制任务在主机组中只执行一次的关键字参数。当我们在编写Ansible任务时,有时候我们希望某个任务只在主机组中的某个主机上执行一次,而不是在每个主机上都执行。 以下是run_once参数的详细说明和用法&#xf…...

短视频矩阵系统源码开发流程​

一、视频矩阵系统源码开发流程分为以下几个步骤: 四、技术开发说明: 产品原型PRD需求文档产品交互流程图部署方式说明完整源代码源码编译方式说明三方框架和SDK使用情况说明和代码位置平台操作文档程序架构文档 一、抖音SEO矩阵系统源码开发流程分为以…...

vite+vue3 css scss PC移动布局自适应

1. 安装 postcss-pxtorem 和 autoprefixer npm install postcss-pxtorem autoprefixer --save2. vite.config.js引入并配置 import postCssPxToRem from postcss-pxtorem import autoprefixer from autoprefixerexport default defineConfig({base: ./,resolve: {alias},plug…...

BLE配对和绑定

参考:一篇文章带你解读蓝牙配对绑定 参考:BLE安全之SM剖析(1) 参考:BLE安全之SM剖析(2) 参考:BLE安全之SM剖析(3) 目录 前言基本概念解读Paring(配对)Bonding(绑定)STK短期秘钥、LTK长期秘钥等 …...

无涯教程-jQuery - html( val )方法函数

html(val)方法设置每个匹配元素的html内容。此属性在XML文档上不可用。 html( val ) - 语法 selector.html( val ) 这是此方法使用的所有参数的描述- val - 这是要设置的html内容。 html( val ) - 示例 以下是一个简单的示例&#xff0c;简单说明了此方法的用法- <…...

【单链表OJ题:删除链表中等于给定值 val 的所有节点】

1.删除链表中等于给定值 val 的所有节点 题目来源 给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所有满足 Node.val val 的节点&#xff0c;并返回 新的头节点 。 /*** Definition for singly-linked list.* struct ListNode {* int val;* s…...

vue element ui web端引入百度地图,并获取经纬度

最近接到一个新需要&#xff0c;要求如下&#xff1a; 当我点击选择地址时&#xff0c;弹出百度地图&#xff0c; 效果如下图&#xff1a; 实现方法&#xff1a; 1、首先要在百度地图开放平台去申请一个账号和key 2、申请好之后&#xff0c;在项目的index.html中引入 3、…...

25.10 matlab里面的10中优化方法介绍—— 函数fmincon(matlab程序)

1.简述 关于非线性规划 非线性规划问题是指目标函数或者约束条件中包含非线性函数的规划问题。 前面我们学到的线性规划更多的是理想状况或者说只有在习题中&#xff0c;为了便于我们理解&#xff0c;引导我们进入规划模型的一种情况。相比之下&#xff0c;非线性规划会更加贴近…...

赛效:如何将PDF文件免费转换成Word文档

1&#xff1a;在网页上打开wdashi&#xff0c;默认进入PDF转Word页面&#xff0c;点击中间的上传文件图标。 2&#xff1a;将PDF文件添加上去之后&#xff0c;点击右下角的“开始转换”。 3&#xff1a;稍等片刻转换成功后&#xff0c;点击绿色的“立即下载”按钮&#xff0c;将…...

java 8 的Stream API

Java 8中引入了Stream API&#xff0c;它是一种处理集合数据的新方式&#xff0c;可以用来处理集合中的元素。Stream API通过提供一组函数式接口和方法&#xff0c;可以使集合的处理更加简洁、高效和易读。 Stream API的主要特点如下&#xff1a; 延迟执行&#xff1a;Stream …...

TypeChat,用TypeScript快速接入AI大语言模型

TypeChat是C# 和 TypeScript 之父 Anders Hejlsberg全新的开源项目。使用AI在自然语言和应用程序和API之间建立桥梁&#xff0c;并且使用TypeScript。 现在出现了很多大型语言模型&#xff0c;但是如何将这些模型最好地集成到现有的应用程序中&#xff0c;如何使用人工智能来接…...

Dcoker compose单机容器集群编排管理

目录 一、概述 二、compose 部署 lnmp 1.Docker Compose 环境安装 2.YAML 文件格式及编写注意事项 3.Docker Compose配置常用字段 4.Docker Compose 常用命令 5. 配置lnmp集群依赖文件 6.修改docker-compose.yml文件 7.根据yml文件创建lnmp容器 一、概述 Docker compos…...

P5635 【CSGRound1】天下第一(记忆化搜索)

用short类型二维数组防止MLE。这里用的记忆化搜索&#xff0c;如果f[x][y]已经有值了&#xff0c;直接返回这个值。判断error的方法&#xff1a;如果下一次又访问到它&#xff0c;说明出现了循环&#xff0c;这样是永远%不到0的&#xff0c;所以&#xff0c;第一次访问一次f[x]…...

如何维护你的电脑:提升性能和延长使用寿命

如何维护你的电脑&#xff1a;提升性能和延长使用寿命 &#x1f607;博主简介&#xff1a;我是一名正在攻读研究生学位的人工智能专业学生&#xff0c;我可以为计算机、人工智能相关本科生和研究生提供排忧解惑的服务。如果您有任何问题或困惑&#xff0c;欢迎随时来交流哦&…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...