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

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代码如何打包

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

MyBatis学习笔记(十二) —— MyBatis的逆向工程

12、MyBatis的逆向工程 正向工程&#xff1a;先创建Java实体类&#xff0c;由框架负责根据实体类生成数据库表。Hibernate是支持正向工程的。 逆向工程&#xff1a;先创建数据库表&#xff0c;由框架负责根据数据库表&#xff0c;反向生成如下资源&#xff1a; Java实体类Mappe…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

从零开始了解数据采集(二十八)——制造业数字孪生

近年来&#xff0c;我国的工业领域正经历一场前所未有的数字化变革&#xff0c;从“双碳目标”到工业互联网平台的推广&#xff0c;国家政策和市场需求共同推动了制造业的升级。在这场变革中&#xff0c;数字孪生技术成为备受关注的关键工具&#xff0c;它不仅让企业“看见”设…...

【汇编逆向系列】六、函数调用包含多个参数之多个整型-参数压栈顺序,rcx,rdx,r8,r9寄存器

从本章节开始&#xff0c;进入到函数有多个参数的情况&#xff0c;前面几个章节中介绍了整型和浮点型使用了不同的寄存器在进行函数传参&#xff0c;ECX是整型的第一个参数的寄存器&#xff0c;那么多个参数的情况下函数如何传参&#xff0c;下面展开介绍参数为整型时候的几种情…...

2025 后端自学UNIAPP【项目实战:旅游项目】7、景点详情页面【完结】

1、获取景点详情的请求【my_api.js】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http(/login/getWXSessionKey, {code,avatar}); };//…...