当前位置: 首页 > 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…...

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

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

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...