Leetcode—环形链表
前言:给定一个链表,判断是否为循环链表并找环形链表的入口点
首先我们需要知道什么是双向循环链表,具体如下图所示。
对于链表,我们如何去判断链表是循环链表呢?又寻找入环点呢?我们可以利用快慢指针的方法,即慢指针一次走一步,快指针一次走两步,两个指针从链表其实位置开始运行,如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。为什么呢?原理是什么呢?我们利用图解分析一波?
问题2:如果slow走一步,fast走三步,他们还会相遇吗?会不会错过呢?我们图解分析一下:
开始追击的时候,他们fast每走一次,他们之间的距离就会缩小2,这时候就要分N奇偶的情况了,为偶的话一定会相遇,为奇的话,每次减少2步,最后fast会超越slow一步,假设环的周长是C的话也就是 fast和slow之间 会相距C - 1步,这时候又要分C-1奇偶情况,为偶数的话,一定会相遇,为奇数的话,就会陷入奇数循环,永远不会为偶。也就不会相遇。
问题3:如何找入口点呢?
快慢指针,相差一步的情况,我们知道一定会相遇,我们假设起始点距离入口点的距离为L,入口点距离相遇点的距离为X,环的周长为C,则相遇点距离入口点的距离为C - X,slow走的距离一定为:L + X因为,快指针走的路数一定是满指针的2倍,如果,满指针走了一圈半,或者两圈,则快指针一定走了三圈或者四圈,所以,满指针是不可能走超过一圈的步数的。那快指针呢?快指针走了多少呢?是 L + C + X ?因为是慢指针步数的二倍,所以是 2 * (L + X) = L + C + X 推出来L = C - X ?这真的合理吗 肯定是不合理的 我们可以画个图推翻它,如下所示:
当环很小的时候,譬如只有两个节点,而L为10个节点 fast每次两步,都绕九个环了,慢指针才进环,所以上面的推理是不合理的。
fast正确走的步数应该是 L + n * C + X,根据二倍的关系的话。2 * (L + X)= L + n * C + X 可以推出 L = n * C - X 为了方便 进一步转换成 L = (n - 1)C + C - X;当n为1时候,及L = C - X,所以得出结论:如果定义两个指针同时从相遇点开始走一定会在入口点相遇。详细代码如下:
解题思路:
如果链表存在环,则fast和slow会在环内相遇,定义相遇点到入口点的距离为X,定义环的长度为C,定义头到入口的距离为L,fast在slow进入环之后一圈内追上slow,则会得知:
slow所走的步数为:L + X
fast所走的步数为:L + X + N * C
并且fast所走的步数为slow的两倍,故:
2*(L + X) = L + X + N * C
即: L = N * C - X
所以从相遇点开始slow继续走,让一个指针从头开始走,相遇点即为入口节点
*/
typedef struct ListNode Node;
struct ListNode *detectCycle(struct ListNode *head) {Node* slow = head;Node* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;//走到相遇点if(slow == fast){// 求环的入口点Node* meet = slow;Node* start = head;while(meet != start){meet = meet->next;start = start->next;}return meet;}}return NULL;
}
相关文章:

Leetcode—环形链表
前言:给定一个链表,判断是否为循环链表并找环形链表的入口点 首先我们需要知道什么是双向循环链表,具体如下图所示。 对于链表,我们如何去判断链表是循环链表呢?又寻找入环点呢?我们可以利用快慢指针的方法…...

蓝牙耳机哪个戴的最舒服?久戴不累的蓝牙耳机推荐
在喧嚣的时代中,快节奏和疲惫充斥着我们的生活,于是耳机成为了人们必不可少的东西,无论是闲暇时亦或是正处在工作时,都会将它戴上,出门在外戴耳机变成了常态,所以小编就整理了一期久戴不累的蓝牙耳机。 No…...
25k的Java开发常问的AQS问题有哪些?
前言:面试高频的AQS问题大多。本文将以实战面试角度出发,将面试官喜欢问的一些问题罗列出来。 文章目录 AQSAQS定义底层实现独占锁举例底层实现独占锁超时获取锁共享锁举例共享锁实现原理作者辟谣AQS AQS定义 AQS的全称是AbstractQueuedSynchronizer,也就是抽象队列同步器…...

Grafana 监控面板绘制流程
本篇作者:IoTDB 社区 -- 张洪胤本文以 IoTDB V1.0.1 版本为例本文档介绍了 Apache IoTDB 监控指标通过 Prometheus 的方式进行采集,并且使用 Grafana 的方式进行可视化。1监控指标的 Prometheus 格式说明对于 Metric Name 为 name, Tags 为 K1V1, ..., K…...
一句话设计模式5:责任链模式
责任链模式:步步为营。 文章目录 责任链模式:步步为营。前言一、责任链模式的作用二、如何实现责任链1 既然是责任链,那么就需要一个链路的承载体 ChainBody2 责任链中每一步都是一个抽象类,因为承载体仅仅是构造链路顺序,里面不放置任何具体业务逻辑:步骤抽象类3 具体步骤执行…...

保姆级使用PyTorch训练与评估自己的EVA网络教程
文章目录前言0. 环境搭建&快速开始1. 数据集制作1.1 标签文件制作1.2 数据集划分1.3 数据集信息文件制作2. 修改参数文件3. 训练4. 评估5. 其他教程前言 项目地址:https://github.com/Fafa-DL/Awesome-Backbones 操作教程:https://www.bilibili.co…...

Java--JMH--性能测试--测试软件运行效率/时间--StopWatch
写在前面: 很多时候想要测试代码运行时间,或者比较2个运行的效率。 最简单的方法就是Sytem.currentTimeMillis记录2开始和结束时间来算 但是Java 代码越执行越快,放在后面的方法会有优势,这个原因受留个眼,以后研究。大概有受类加…...

JavaScript Array(数组)对象
数组对象的作用是:使用单独的变量名来存储一系列的值。参数参数 size 是期望的数组元素个数。返回的数组,length 字段将被设为 size 的值。参数 element ...; elementn 是参数列表。当使用这些参数来调用构造函数 Array() 时,新创建的数组的元…...
干货 | 电容在电路35个基本常识
第1个电压源正负端接了一个电容,与电路并联,用于整流电路时,具有很好的滤波作用,当电压交变时,由于电容的充电作用,两端的电压不能突变,就保证了电压的平稳。当用于电池电源时,具有交…...

日读300篇文献的技巧
感觉自己看文章很慢,有时候也抓不住重点。 如果是英文文献的话,可能还要有点难度,毕竟英语渣渣还是需要有中文-》英文的转换过程。 最近在搞毕业论文的时候,发现了一个非常好玩的东西,大大提升了我看文章搞科研&#x…...

C++核心编程
一、内存分区模型概述:C程序在执行时,将内存划分为4个区域程序运行前:代码区:存放函数体的二进制代码,由操作系统管理①共享。共享的目的是对于频繁被执行的程序,在内存中只需有一份代码即可②只读。使其只…...

SpringMVC程序开发
目录 SpringMVC 1、MVC定义 2、MVC和SpringMVC之间的关系 学SpringMVC 1、Spring MVC的创建和连接 浏览器获取前端接口和后端程序连接功能实现 2、获取参数 2.1、传递单个参数/多个参数 2.2、传递对象 2.3、传递表单参数 2.4、后端参数重命名 2.5、RequestBody接收J…...
多版本并发控制MVCC
什么是MVCC? MVCC是一种并发控制方法,一般在数据库管理系统中,实现数据库的并发访问。 可以使用乐观锁和悲观锁来实现。 MVCC的作用? 可以在不加锁的情况下解决读写问题,同时还可以解决脏读,幻读&#…...

JavaScript Date(日期)对象
日期对象用于处理日期和时间。在线实例返回当日的日期和时间如何使用 Date() 方法获得当日的日期。getFullYear()使用 getFullYear() 获取年份。getTime()getTime() 返回从 1970 年 1 月 1 日至今的毫秒数。setFullYear()如何使用 setFullYear() 设置具体的日期。toUTCString()…...

【Python】AES加解密代码,文章还有加密串等你来解密,等你来挑战
🍦🍦写这篇AES文章也是有件趣事,有位小伙伴发了段密文,看看谁解密速度快,学过Python的小伙伴一下子就解开来了,内容也挺有趣的。 🍟🍟原来加解密也可以这么有趣,虽然看起…...
代码随想录【Day34】| 1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果
1005. K 次取反后最大化的数组和 题目链接 题目描述: 给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。&…...

Java性能调优杀手锏JMH
JMH简介 JMH(Java Microbenchmark Harness)由 OpenJDK/Oracle 里面那群开发了 Java编译器的大牛们所开发,是一个功能强大、灵活的工具,它可以用于检测和评估Java应用程序的性能,主要目的是测量Java应用程序的性能,尤其是在多线程…...

实现excle表上传生成echarts图
代码如下html <!--这是一个网上关于读取Excel最经典的代码--> <!DOCTYPE html> <html><head><meta charset"utf-8"><title>ECharts</title><!-- 引入 echarts.js --><!-- <script src"newjs/js/incubato…...

python代码如何打包
网上的文章对小白都不太友好呀,讲得都比较高大上,本文章就用最简单的方式来教会大家如何打包。既然各位已经学习到了python打包了, 深适度应该跟我查不多。 注意事项: 1. 这个插件只能打包 mac 、win系统运行的文件,也…...

MyBatis学习笔记(十二) —— MyBatis的逆向工程
12、MyBatis的逆向工程 正向工程:先创建Java实体类,由框架负责根据实体类生成数据库表。Hibernate是支持正向工程的。 逆向工程:先创建数据库表,由框架负责根据数据库表,反向生成如下资源: Java实体类Mappe…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...