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

判断链表有环的证明

目录

1.问题      

2.证明

3.代码实现


1.问题      

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

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

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

         

2.证明

        使用快慢指针的方法可以很简单的达到目的,慢指针每次走一步快指针每次走两步,如果在链表中存在环,入环以后快慢指针没走一次,他们直接的距离就会减一,直至最后它们会在环里面相遇,如图: 

        思考一个问题,快指针必须走两步吗,快指针每次走三步行不行,四步呢?五步呢?N步行不行?

        假设快指针每次走三步,当慢指针入环时,它们同时向后走,每次它们之间的距离会减少2,但是如果它们之间的距离是奇数,那么他们这次就不会相遇,极限清空下,他们每次的距离都是奇数的话,那么他们是不是就永远不会相遇了,走N步的道理也是一样的。如图:

 

3.代码实现

typedef struct ListNode Node;
bool hasCycle(struct ListNode *head) 
{//金典的快慢指针法//快指针每次走两步,慢指针每次走一步,//快指针先进环,慢指针后进环//在环的里面每走一次快慢指针直接的距离缩小1//最终快指针会追上慢指针//如果最终不想交说明链表没有环Node* slow = head;Node* fast = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(slow == fast){//在环里面相遇return true;}}return  false;
}

相关文章:

判断链表有环的证明

目录 1.问题 2.证明 3.代码实现 1.问题 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用…...

百度屏蔽词有哪些?其中就有移民关键词指数被屏蔽?

我是百收网SEO,点点上面的头像,欢迎关注我哦! 今日tombkeeper消息爆料:百度指数已经屏蔽“移民”等关键词指数。 大家好,我是百收网SEO商学院的狂潮微课老师,今天我们来讲解第 12 节课关键词优化难度分析…...

代码随想录day02

977.有序数组的平方 ● 力扣题目链接 ● 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 思路 ● 暴力排序,时间复杂度O(n nlogn) ● 使用双指针,时间复杂度O(n) …...

VR时代真的到来了?

业界对苹果的期待是,打造一台真正颠覆性的,给头显设备奠定发展逻辑底座的产品,而实际上,苹果只是发布了一台更强大的头显。 大众希望苹果回答的问题是“我为什么需要一台AR或者VR产品?”,但苹果回答的是“…...

docker run 命令转化为 docker-compose 工具

工作当中需要将 docker run 转换为更方便的 docker-compose 格式,可以使用下面的工具来完成。 转换工具:https://www.composerize.com/?utm_sourceappinn.com 使用介绍:https://www.appinn.com/composerize-for-docker-compose/...

php如何对接伪原创api

在了解伪原创api的各种应用形态之后,我们继续探讨智能写作背后的核心技术。需要说明的是,智能写作和自然语言生成、自然语言理解、知识图谱、多模算法等各类人工智能算法都有紧密的关联,在百度的智能写作实践中,常根据实际需求将多…...

设计模式行为型——模板模式

目录 模板模式的定义 模板模式的实现 模板模式角色 模板模式类图 模板模式举例 模板模式代码实现 模板模式的特点 优点 缺点 使用场景 注意事项 实际应用 模板模式的定义 模板模式(Template Pattern)属于行为型设计模式,又叫模版…...

12.Eclipse导入Javaweb项目

同事复制一份他的项目给我ekp.rar (懒得从SVN上拉取代码了)放在workspace1目录下 新建一个文件夹 workspace2,Eclipse切换到workspace2工作空间 选择Import导入 选择导入的项目(这里是放到workspace1里面) 拷贝一份到workspace2里面 例子 所有不是在自己电脑上开发…...

探索自动化网页交互的魔力:学习 Selenium 之旅【超详细】

"在当今数字化的世界中,网页自动化已经成为了不可或缺的技能。想象一下,您可以通过编写代码,让浏览器自动执行各种操作,从点击按钮到填写表单,从网页抓取数据到进行自动化测试。学习 Selenium,这一功能…...

css常用样式和不常用样式

文章目录 1、hover鼠标变小手2、ul去除点3、文字溢出显示省略号(1)一行文字溢出显示省略号(2)多行文字溢出显示省略号 4、文字单词超出(1)文字单词超出换行(word-wrap)(2…...

【小练习】交互式网格自定义增删改错误记录及解决(进行中)

经过之前的学习,已经能创建简单的交互式网格并设置自定义增删改按钮,但是实现上还是存在一些问题,来完善优化一下。 首先是修改,正常修改都会弹出修改框,里面是之前存储的信息,根据实际需要对其进行修改&a…...

云渲染效果不对?云渲染前的四个细节表明你的问题出在这里!

云渲染针对3D渲染行业,帮助本地电脑解决渲染慢的问题,大幅提高设计师的工作效率。但小编发现,有不少小伙伴在使用云渲染时,出现了渲染效果不对或丢失的问题,根据小伙伴们的问题和我们创意云云渲染平台给出的解决方案&a…...

翻转二叉树

声明 该系列文章仅仅展示个人的解题思路和分析过程,并非一定是优质题解,重要的是通过分析和解决问题能让我们逐渐熟练和成长,从新手到大佬离不开一个磨练的过程,加油! 原题链接 翻转二叉树备战技术面试?…...

检测新突破 | AlignDet:支持各类检测器自监督新框架(ICCV2023)

引言 论文链接:https://arxiv.org/abs/2307.11077 项目地址:https://github.com/liming-ai/AlignDet 这篇论文主要研究目标检测领域的自监督预训练方法。作者首先指出,当前主流的预训练-微调框架在预训练和微调阶段存在数据、模型和任务上的…...

03.Show and Tell

目录 前言泛读摘要IntroductionRelated Work小结 精读模型基于LSTM的句子生成器TrainingInference 实验评价标准数据集训练细节分数结果生成结果多样性讨论排名结果人工评价结果表征分析 结论 代码 前言 本课程来自深度之眼《多模态》训练营,部分截图来自课程视频。…...

QStackedWidget 的使用

QStackedWidget QStackedWidget 提供一些层叠的 Widget,同一时间只有一个Widget处于可视状态,就像书本一样。 什么时候使用 QStackedWidget 强烈建议 如果需要点击一个按钮显示一些界面再点击按钮隐藏当前界面而去显示另外的界面时。都使用 QStackedW…...

大数据--难点--地图的制作

地图一直是亮点也是难点,刚刚进公司的时候也很难懂~~做出来的也很难看 纯CSS3使用vw和vh视口单位实现h5页面自适应,gulp自动监听sass改动并保存到css中 当修改了sass里面的代码后,gulp会自动监听修改内容并同名保存到css文件夹中&#xff0…...

【AI作画】使用Stable Diffusion的艺术二维码完全生成攻略

文章目录 前言Stable Diffusion 简介 什么是云端平台?优势灵活性和可扩展性成本效益高可用性和容错性管理简便性 选择适合的云端平台 平台优势平台操作购买算力并创建工作空间启动工作空间应用市场一键安装 使用Stable-Diffusion作图使用控制网络将文本转图像二维码…...

SQLAlchemy------更多查询

1 查询: filer:写条件 filter_by:等于的值 res session.query(User).all() # 是个普通列表 print(type(res)) print(len(res)) all()的结果就是列表,列表里面是对象 2 只查询某几个字段 # select name as xx,email from user; res…...

13-数据结构-串以及KMP算法,next数组

串 目录 串 一、串: 二、串的存储结构: 三、模式匹配 1.简单模式匹配(BF算法) 2.KMP算法 2.1-next(j)数组手工求解 2.2-nextval(j)数组手工求解 一、串: 内容受…...

【JavaEE】-- HTTP

1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...

go 里面的指针

指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略(地理位置/文件) 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型,核心实现方式: 标准消息类型:直接使用 SDK 内置类型(文件、图片等)自…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具,专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑(如DBC、LDF、ARXML、HEX等),并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...

项目进度管理软件是什么?项目进度管理软件有哪些核心功能?

无论是建筑施工、软件开发,还是市场营销活动,项目往往涉及多个团队、大量资源和严格的时间表。如果没有一个系统化的工具来跟踪和管理这些元素,项目很容易陷入混乱,导致进度延误、成本超支,甚至失败。 项目进度管理软…...

中国政务数据安全建设细化及市场需求分析

(基于新《政务数据共享条例》及相关法规) 一、引言 近年来,中国政府高度重视数字政府建设和数据要素市场化配置改革。《政务数据共享条例》(以下简称“《共享条例》”)的发布,与《中华人民共和国数据安全法》(以下简称“《数据安全法》”)、《中华人民共和国个人信息…...

VUE3 ref 和 useTemplateRef

使用ref来绑定和获取 页面 <headerNav ref"headerNavRef"></headerNav><div click"showRef" ref"buttonRef">refbutton</div>使用ref方法const后面的命名需要跟页面的ref值一样 const buttonRef ref(buttonRef) cons…...

Angular中Webpack与ngx-build-plus 浅学

Webpack 在 Angular 中的概念 Webpack 是一个模块打包工具&#xff0c;用于将多个模块和资源打包成一个或多个文件。在 Angular 项目中&#xff0c;Webpack 负责将 TypeScript、HTML、CSS 等文件打包成浏览器可以理解的 JavaScript 文件。Angular CLI 默认使用 Webpack 进行项目…...

python学习day39

图像数据与显存 知识点回顾 1.图像数据的格式&#xff1a;灰度和彩色数据 2.模型的定义 3.显存占用的4种地方 a.模型参数梯度参数 b.优化器参数 c.数据批量所占显存 d.神经元输出中间状态 4.batchisize和训练的关系 import torch import torchvision import torch.nn as nn imp…...