OJ——环形链表

环形链表概念

环形链表是一种特殊类型的链表数据结构,其最后一个节点的地址域不为null,而是指向了链表中的某个节点,形成一段闭环,如下图:

tip:该类型题目不能以判断 cur.next 是否为 null 为循环条件,否则死循环

判断是否为环形链表

给一个链表的头节点 head ,判断链表中是否有环,如果链表中存在环 ,则返回 true 。 否则,返回 false 。

思路:

  • 使用快慢指针(fast、slow),快指针每次移动两步,慢指针每次移动一步,两指针从链表起始位置走,若链表带环,则一定相遇
  • 以 fast != null (对应偶数节点情况) && fast.next != null (对应奇数节点情况) 为循环条件
  • 若 fast 与 slow 相遇,则是环形链表,返回 true
  • 若循环结束,则未相遇,即不是环形链表,返回 false

 代码:

    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }

扩展:若快指针走3步、4步、n步是否可行

假设快指针每次走三步,慢指针每次走一步,此时快指针先进环,慢指针后进环,假设慢指针进环时,快指针的位置如下图所示:

这种情况下,快指针每次走3步,慢指针每次走1步,快指针刚好将慢指针套圈,永远不会相遇

当快指针每次走3步,慢指针每次走2步,他们差值为1,此时才会相遇

但是循环条件就要发生改变:

while(fast.next != null && fast.next.next != null) {

这样代码更复杂,得不偿失,因此最优解为快指针每次走2步,慢指针每次走1步

环形链表求入口点

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

 思路:这里涉及到一个简单的数学问题,如下图:

假设环的长度为C,起始点到入口点的距离为X,相遇点到入口点的距离为Y

快指针每次走2步,慢指针每次走1步,当他们相遇时,快指针走的步数是慢指针的2倍,所以得出以下等式:

(slow所走路程的2倍) 2* (X + C - Y) = X + C + (C - Y) (fast所走的路程)

计算可得 X = Y

说明起始点到入口点的距离 和 相遇点到入口点的距离是相同的

当我们以相同速度一个从起始点出发,一个从相遇点出发,再次相遇就是入口点

代码:

    public ListNode detectCycle(ListNode head) {
        //先求相遇点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                break;
            }
        }
        if(fast == null || fast.next == null) {
            return null;
        }
        
        //让fast回到起始点,以和slow一样的速度往后走
        //slow从相遇点开始走
        fast = head;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;//该fast即为入口点
    }

另一种情况:环的长度远远小于起始点到入口点的长度,即Y不等于X

这种情况下,假设slow绕环N次后与fast在相遇点处相遇,距离公式变为:

(slow所走路程的2倍) 2* (X + C - Y) = X + NC + (C - Y) (fast所走的路程)

计算可得:X = (N-1)*C + Y

当N等于1时,就是上面 X = Y 的例子,X = Y 是所有情况中的一种特殊情况,代码无需改动

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/702310.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2024 Python-Flask框架:网页版 邮件超时自动提醒器(超简单)

首先安装flask框架 pip install flask pip install pywin32 pip install pandas pip install datetime 然后根目录下,创建 app.py 和 templates文件夹 (注意我们的原时间是年,周,日的计算方式) from flask import …

Windows10安装配置Docker客户端和WSL2与Hyper-V虚拟机

一、需求说明 需要在Windows系统中安装配置Docker的客户端,方便直接管理配置docker镜像容器内容。 二、Windows10安装Docker客户端步骤 2.1、下载安装Docker客户端 对于Windows 10以下的用户,推荐使用Docker Toolbox Windows安装文件:http://mirrors.aliyun.com/docker-…

有哪些指标体系搭建模型?五个步骤教你从0开始搭建指标体系

在当今的商业环境中,数据驱动决策已成为企业成功的关键因素。构建一个有效的指标体系是实现数据驱动的基石,它能够帮助企业明确业务目标、量化业绩表现、监控市场动态,并指导战略规划。一个精心设计的指标体系能够为企业提供一个全面的视图&a…

社区新标准发布!龙蜥社区标准化 SIG MeetUp 圆满结束

5 月 31 日,「龙蜥社区“走进系列”」第 9 期之走进阿里云于北京圆满结束。来自阿里云、浪潮信息、红旗软件、中兴通讯|中兴新支点、中科曙光、中科方德、统信软件、麒麟软件、万里红、普华基础软件、飞腾信息、凝思、申威、新华三等公司的 30 余位专家出席会议。会…

腾讯元宝 APP 上线与大模型 AIGC 产品的未来趋势

💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

知识图谱的应用---智慧城建

文章目录 智慧城建典型应用 智慧城建 智慧城建是运用高新技术手段感测、分析、整合城市运行核心系统的各项关键信息,从而对包括民生、环保、公共安全、城市服务、工商业活动在内的各种需求做出智能响应。当前,我国正处于快速城市化的阶段,伴随…

人脸识别之--计算余弦相似度-android

余弦相似度是比对两个向量是否一致,余弦相似度是通过计算两个向量的夹角余弦值来衡量它们之间的相似度,算出来的值可以直接用作相似度的分数。 公式: 余弦相似度和欧式距离经常用来人脸识别特征对比。 其中: 1、余弦相似度是通…

算法导论实战(七)(山东大学软件学院算法历年考题+朋辈辅导)

🌈 个人主页:十二月的猫-CSDN博客 🔥 系列专栏: 🏀算法启示录 💪🏻 十二月的寒冬阻挡不了春天的脚步,十二点的黑夜遮蔽不住黎明的曙光 目录 前言 第一周 题目一 题目二 题目三…

链路层、网络层、传输层和应用层协议详解分析

接上篇文章wireshark抓包分析-CSDN博客wireshark是网络包分析工具网络包分析工具的主要作用是尝试捕获网络包,并尝试显示包的尽可能详细的情况。wireshark应用举例:网络管理员用来解决网络问题网络安全工程师用来检查安全隐患开发人员用来测试协议的执行情况学习网络…

江协科技STM32学习- 2安装Keil5-MDK

本文是根据哔哩哔哩网站上“江协科技STM32”视频的学习笔记,在这里会记录下江协科技STM32开发板的配套视频教程所作的实验和学习笔记内容。本文大量引用了江协科技STM32教学视频和链接中的内容。 引用: STM32入门教程-2023版 细致讲解 中文字幕_哔哩哔哩…

【Python】已解决TypeError: unsupported operand type(s) for ...报错方案合集

😎 作者介绍:我是程序员洲洲,一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博主。 🤓 同时欢迎大家关注其他专栏,我将分享Web前后端开发、人工智能、机器学习、深…

LabVIEW Actor架构特点与适用范围

LabVIEW的Actor架构提供了一种基于消息传递的并行任务管理方式,适合复杂系统的模块化设计。其特点包括高可扩展性、灵活的消息传递和并行处理能力。维护和修改要求较高,适合有一定经验的开发人员。对于中小型项目,可考虑选择更简单的状态机架…

Spring Cloud Bus 消息总线基础入门与实践总结

【1】基础介绍 其主要是实现分布式自动刷新配置功能,Spring Cloud Bus 配合 Spring Cloud Config 使用可以实现配置的动态刷新。Spring Cloud Bus是用来将分布式系统的节点与轻量级消息系统链接起来的框架,它整合了Java的事件处理机制和消息中间件的功能…

锌,能否成为下一个“铜”?

光大期货认为,今年以来,市场关注锌能否接棒铜价牛市。铜需求增长空间大,而锌消费结构传统,缺乏新亮点。虽然在供应的扰动上锌强于铜,但因需求乏善可陈,金融属性弱势,锌很难接棒铜,引…

[数据集][目标检测]中国象棋检测数据集VOC+YOLO格式300张12类别

数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):300 标注数量(xml文件个数):300 标注数量(txt文件个数):300 标注类别…

微信服务号营销新篇章:HubSpot与MessageBox的强强联合

随着全球数字化浪潮的推进,越来越多的企业开始寻求海外市场的拓展机会。在这个过程中,微信服务号作为一个强大的数字化工具,为企业提供了无限的商业可能。本文将详细解析微信服务号的概念、功能、使用方法,以及它与HubSpot、Messa…

2024最新最全【大模型】人工智能零基础入门到精通,看完这一篇就够了!

大模型技术是一个涉及人工智能、机器学习、深度学习等多个领域的复杂课题。学习大模型技术通常需要以下几个步骤: 基础知识学习:首先,需要掌握计算机科学、数据结构和算法的基础知识。此外,对线性代数、概率论和统计学有一定的理…

C#——字典diction详情

字典 字典: 包含一个key(键)和这个key所以对应的value&#xff08;值&#xff09;&#xff0c;字典是是无序的&#xff0c;key是唯一的&#xff0c;可以根据key获取值。 定义字典: new Diction<key的类型&#xff0c;value的类型>() 方法 添加 var dic new Dictionar…

消息队列(MQ)核心知识点(持续更新中)

消息队列&#xff08;MQ&#xff09;核心知识点&#xff08;持续更新中&#xff09; RabbitMQRabbitMQ概念及架构RabbitMQ消息丢失的场景及解决方案RabbitMQ重复消费场景及解决方案RabbitMQ消息堆积场景及解决方案RabbitMQ集群 RocketMQRocketMQ概念及架构 RabbitMQ RabbitMQ概…

Hadoop 2.0:主流开源云架构(三)

目录 四、Hadoop 2.0体系架构&#xff08;一&#xff09;Hadoop 2.0公共组件Common&#xff08;二&#xff09;分布式文件系统HDFS&#xff08;三&#xff09;分布式操作系统Yarn&#xff08;四&#xff09;Hadoop 2.0安全机制简介 四、Hadoop 2.0体系架构 &#xff08;一&…