[C/C++]数据结构 链表OJ题:环形链表(如何判断链表是否有环)

news/2024/3/4 4:16:35

题目描述:

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。


示例:

提示:

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

解题思路:

        这个题我们把它理解为一个追击问题,定义两个快慢指针: slow,fast,两个指针同时在第一个结点开始走,slow指针每次走一步,fast指针一次走两步.

        如果链表有环,当fast走到入环点,slow走到了起始到入环点的一半.继续走,当slow走到如环点时,fast已经在环内的某个位置了,假设slow与fast之间的距离为N

这时每走一步,fast与slow的距离就会减小1,当N减为0时就代表fast追到了slow,两指针相遇就说明链表有环

        如果链表无环,则两指针就不会遇到

我们画个图理解一下:

代码实现:


bool hasCycle(struct ListNode *head) {struct ListNode *slow=head;struct ListNode *fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast)return true;}return false;
}


http://www.ppmy.cn/news/1213126.html

相关文章

Java图像编程之:Graphics

一、概念介绍 1、Java图像编程的核心类 Java图像编程的核心类包括&#xff1a; BufferedImage&#xff1a;用于表示图像的类&#xff0c;可以进行像素级的操作。Image&#xff1a;表示图像的抽象类&#xff0c;是所有图像类的基类。ImageIcon&#xff1a;用于显示图像的类&a…

Maven-依赖管理机制

一、背景和起源 依赖管理是Maven的一个核心功能。管理单模块项目的依赖相对比较容易&#xff0c;管理多模块项目依赖或者有几百个模块项目的依赖就是一个巨大的挑战。 如果手动构建项目&#xff0c;那么就先需要梳理各个模块pom中定义的依赖&#xff0c;然后将依赖下载到本地&…

Spring-Security前后端分离权限认证

前后端分离 一般来说&#xff0c;我们用SpringSecurity默认的话是前后端整在一起的&#xff0c;比如thymeleaf或者Freemarker&#xff0c;SpringSecurity还自带login登录页,还让你配置登出页,错误页。 但是现在前后端分离才是正道&#xff0c;前后端分离的话&#xff0c;那就…

【Linux】八、进程通信

进程通信的介绍 目的 数据传输&#xff1a;一个进程将它的数据发送给另一个进程&#xff1b; 资源共享&#xff1a;多个进程间共享资源&#xff1b; 通知事件&#xff1a;一个进程向另一个或一组进程发送消息&#xff0c;同时事件如&#xff0c;进程终止时要通知父进程&#xf…

敏捷开发是什么?敏捷开发流程是怎么样的?

1. 什么是敏捷开发&#xff1f; 敏捷开发是一种迭代、增量式的软件开发方法&#xff0c;旨在通过灵活、协作和快速响应变化的方式&#xff0c;提高开发团队的效率和产品的质量。相较于传统的瀑布式开发模型&#xff0c;敏捷开发更加注重用户需求的响应和团队协作&#xff0…

Qt绘制饼状图

必须在MainWindow.h头文件开头放 #include <QtCharts> //必须这么设置 创建chart&#xff1a; void MainWindow::iniPiewChart() { //饼图初始化QChart *chart new QChart();chart->setTitle(" Piechart演示");chart->setAnimationOptions(QChar…

docker搭建mysql主从复制

1. 基础环境 环境 名称描述CentOS 7.6Linux操作系统版本docker 20.10.5docker版本mysql 8.0.29mysql镜像版本 节点 节点名称读写/主从地址端口master读节点/主节点192.168.1.6:3306slave1写节点/从节点192.168.1.6:3307slave2写节点/从节点192.168.1.6:3308 2. 主节点 使…

Android Studio里的C/C++返回: ld: error: undefined symbol

文章目录 问题解决参考 问题 Android Studio里的C/C进行编译时返回: ld: error: undefined symbol的错误&#xff0c;进行了解决。 解决 编译环境突然出现了这个问题&#xff0c;尝试解决&#xff0c;终于找到一个解决办法&#xff1a;卸载ndkVersion "23.1.7779620&q…

【fast2021论文导读】 Learning Cache Replacement with Cacheus

文章:Learning Cache Replacement with Cacheus 导读摘要: 机器学习的最新进展为解决计算系统中的经典问题开辟了新的、有吸引力的方法。对于存储系统,缓存替换是一个这样的问题,因为它对性能有巨大的影响。 本文第一个贡献,确定了与缓存相关的特征,特别是,四种工作负载…

55基于matlab的1.高斯噪声2.瑞利噪声3.伽马噪声4.均匀分布噪声5.脉冲(椒盐)噪声

基于matlab的1.高斯噪声2.瑞利噪声3.伽马噪声4.均匀分布噪声5.脉冲&#xff08;椒盐&#xff09;噪声五组噪声模型&#xff0c;程序已调通&#xff0c;可直接运行。 55高斯噪声、瑞利噪声 (xiaohongshu.com)

刚柔相济铸伟业 ——访湖南顺新金属制品科技有限公司董事长张顺新

时代在变&#xff0c;唯初心不改。 精致、谦虚、谨慎、儒雅、温和——他就是张顺新&#xff0c;湖南顺新金属制品科技有限公司、湖南顺新供应链管理有限公司董事长&#xff0c;民建长沙市委常委&#xff0c;民建湖南省环资委副主任&#xff0c;省、市民建企联会常务副会长&…

【Redis】set 集合

上一篇&#xff1a;list 列表 https://blog.csdn.net/m0_67930426/article/details/134364315?spm1001.2014.3001.5501 目录 Sadd Smembers Sismember Scard Srem ​编辑Srandomember Spop Smove 集合类 Sdiff Sinter Sunion 官网 https://redis.io/commands/?…

2023-11-12

今日比较摆烂, 但是把自写管道的原理搞懂了, 主要是把 exp 完完全全看懂了, 还不错. 然后就没干啥了. 明日计划: 学校的作业. AFL 源码. 我真是服了我自己了, AFL 源码搁多久了, 操操操 然后把 seccomp 重新学习下

NestJS——基于Node.js 服务器端应用程序的开发框架

文章目录 前言什么是 NestJS&#xff1f; 一、NestJS特性&#xff1f;二、使用步骤Typescript 知识后端开发基本知识新建项目目录结构 前言 Nestjs中文文档 什么是 NestJS&#xff1f; Nest (NestJS) 是一个用于构建高效、可扩展的 Node.js 服务器端应用程序的开发框架。它利用…

KubeSphere 社区双周报 | KubeSphere 3.4.1 发布 | 2023.10.27-11.09

KubeSphere 社区双周报主要整理展示新增的贡献者名单和证书、新增的讲师证书以及两周内提交过 commit 的贡献者&#xff0c;并对近期重要的 PR 进行解析&#xff0c;同时还包含了线上/线下活动和布道推广等一系列社区动态。 本次双周报涵盖时间为&#xff1a;2023.10.27-2023.…

Javaweb之javascript的小案例的详细解析

1.5.4 案例 1.5.4.1 需求说明 鲁迅说的好&#xff0c;光说不练假把式,光练不说傻把式。所以接下来我们需要通过案例来加强对于上述DOM知识的掌握。需求如下3个&#xff1a; 点亮灯泡 将所有的div标签的标签体内容后面加上&#xff1a;very good 使所有的复选框呈现被选中的…

时间序列预测实战(九)PyTorch实现LSTM-ARIMA融合移动平均进行长期预测

一、本文介绍 本文带来的是利用传统时间序列预测模型ARIMA(注意&#xff1a;ARIMA模型不属于机器学习)和利用PyTorch实现深度学习模型LSTM进行融合进行预测&#xff0c;主要思想是->先利用ARIMA先和移动平均结合处理数据的线性部分&#xff08;例如趋势和季节性&#xff09…

Linux进程的认识与了解[上]

文章目录 1.何为进程?1.1对进程的认识1.2基本概念 2.OS如何管理大量进程?2.1图解2.2进程的形成 3.何为PCB?3.1对PCB的认识3.2task_ struct内容分类3.2对进程表的认识 4.查看进程4.1基础指令4.2获取某进程的PID(process id)4.3杀死进程4.4获取当前进程的父进程的ppid(parent …

【STM32】STM32Cube和HAL库使用初体验

1.STM32Cube和HAL库模式开发流程 1、流程介绍 (1)环境搭建&#xff1a;STM32CubeMX安装、STM32xxFW安装、MDK5安装、pack包安装【顺序很重要】 【STM32】STM32的Cube和HAL生态-CSDN博客中的3.STM32CubeMX工具入门 (2)STM32CubeMX中创建工程&#xff0c;选择芯片型号&#xff0…

Scrum Master 如何更好的支持PO?

在过去几年中&#xff0c;和许多Scrum Master交流时&#xff0c;我遇到一个令人担忧的模式。虽然我们有Scrum指南和其他补充资源&#xff0c;许多Scrum Master&#xff0c;特别是刚起步的Scrum Master们&#xff0c;还在日复一日的为如何帮助Product Owner而挣扎着。 以下是我…
最新文章