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

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...