LeetCode 141. 环形链表
原题链接
难度:easy\color{Green}{easy}easy
题目描述
给你一个链表的头节点 headheadhead ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 nextnextnext 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pospospos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 注意:pospospos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 truetruetrue 。 否则,返回 falsefalsefalse 。
示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
提示:
- 链表中节点的数目范围是 [0,104][0, 10^{4}][0,104]
- −105<=Node.val<=105-10^{5} <= Node.val <= 10^{5}−105<=Node.val<=105
- pospospos 为 −1-1−1 或者链表中的一个 有效索引 。
进阶: 你能用 O(1)O(1)O(1)(即,常量)内存解决此问题吗?
算法
(链表、指针扫描)
用两个指针从头开始扫描,第一个指针每次走一步,第二个指针每次走两步。如果走到 null,说明不存在环;否则
如果两个指针相遇,则说明存在环。
为什么呢?
假设链表存在环,则当第一个指针走到环入口时,第二个指针已经走到环上的某个位置,距离环入口还差 xxx 步。
由于第二个指针每次比第一个指针多走一步,所以第一个指针再走 xxx 步,两个指针就相遇了。

时间复杂度
第一个指针在环上走不到一圈,所以第一个指针走的总步数小于链表总长度。而第二个指针走的路程是第一个指针
的两倍,所以总时间复杂度是 O(n)O(n)O(n)
C++ 代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {if (!head || !head->next) return false;auto s = head, f = head->next;while (f) {s = s->next, f = f->next;if (!f) return false;f = f->next;if (s == f) return true;}return false;}
};
相关文章:
LeetCode 141. 环形链表
原题链接 难度:easy\color{Green}{easy}easy 题目描述 给你一个链表的头节点 headheadhead ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 nextnextnext 指针再次到达,则链表中存在环。 为了表示给定链表中的…...
git提交
文章目录关于数据库:桌面/vue-admin/vue_shop_api 的 git 输入 打开 phpStudy ->mySQL管理器 导入文件同时输入密码,和文件名 node app.js 错误区: $ git branch // git branch 查看分支 只有一个main分支不见master解决: gi…...
Java中常见的编码集问题
收录于热门专栏Java基础教程系列(进阶篇) 一、遇到一个问题 1、读取CSV文件 package com.guor.demo.charset;import java.io.BufferedReader; import java.io.FileReader; import java.util.ArrayList; import java.util.HashMap; import java.util.L…...
数据结构与算法(Java版) | 就让我们来看看几个实际编程中遇到的问题吧!
上一讲,我给大家简单介绍了一下数据结构,以及数据结构与算法之间的关系,照理来说,接下来我就应该要给大家详细介绍线性结构和非线性结构了,但是在此之前,我决定还是先带着大家看几个实际编程中遇到的问题&a…...
【C++算法】dfs深度优先搜索(上) ——【全面深度剖析+经典例题展示】
💃🏼 本人简介:男 👶🏼 年龄:18 📕 ps:七八天没更新了欸,这几天刚搞完元宇宙,上午一直练🚗,下午背四级单词和刷题来着,还在忙一些学弟…...
总结高频率Vue面试题
目录 什么是三次握手? 什么是四次挥手?(close触发) 什么是VUEX? 什么是同源----跨域? 什么是Promise? 什么是fexl布局? 数据类型 什么是深浅拷贝? 什么是懒加载&…...
IP协议详解
目录 前言: IP协议 提出问题 解决方案 地址管理 子网掩码 路由选择 小结: 前言: IP协议作为网络层知名协议。当数据经过传输层使用TCP或者UDP对数据进行封装,然后当数据到达网络层,基于TCP或UDP数据包继续进行…...
webpack5 基础配置
在开发中,我们会使用 vue、react、less、scss等语法进行开发项目,但是浏览器只能识别 js、css,或者说在js中使用了es6中的import 导入 这时候也需要打包工具去转换成浏览器可以识别的语句。 一、使用webpack 1.初始化package.json npm i…...
IDEA入门安装使用教程
一、背景 作为一个Java开发者,有非常多编辑工具供我们选择,比如Eclipse、IntelliJ IDEA、NetBeans、Visual Studio Code、Sublime Text等等,这些有免费也有收费的,但是就目前市场占比来说普遍使用Eclipse和IntelliJ IDEA这两款主…...
Lambda表达式使用及详解
一 Lambda表达式的简介 Lambda表达式(闭包):java8的新特性,lambda运行将函数作为一个方法的参数,也就是函数作为参数传递到方法中。使用lambda表达式可以让代码更加简洁。 Lambda表达式的使用场景:用以简…...
JAVA练习52-打家劫舍
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 一、题目-打家劫舍 1.题目描述 2.思路与代码 2.1 思路 2.2 代码 总结 前言 提示:这里可以添加本文要记录的大概内容: 2月16日练习内容 提…...
简单谈一谈幂等测试
1、什么是幂等测试 幂等是一个抽象的概念,在编程中一个幂等操作的特点是其任意多次执行所产生的影响均与一次执行的影响相同,即多次调用方法或者接口不会改变业务状态,可以保证重复调用的结果和单次调用的结果一致。幂等测试,则主…...
typescript复习笔记
数组类型-限定每一项的类型 //写法一 const arrNumber: number[] [1, 2, 3] const arrString: string[] [a, b, c] //写法二 const arrNumber2: Array<number> [1, 2, 3] const arrString2: Array<string> [a, b, c]联合类型 符号是 | //数组可以存放字符串或…...
webstorm开发electron,调试主进程方案
官网教程地址:https://www.electronjs.org/zh/docs/latest/tutorial/debugging-main-process 我只能说官网太看得起人了,整这么简易的教程…… 命令行开关 第一步还是要按要求在我们的package.json里加上端口监听:–inspect5858 我的命令…...
2W字正则表达式基础知识总结,这一篇就够了!!(含前端常用案例,建议收藏)
正则表达式 (Regular Expression,简称 RE 或 regexp ) 是一种文本模式,包括普通字符(例如,a 到 z 之间的字母)和特殊字符(称为"元字符")正则表达式使用单个字符串来描述、匹配一系列匹…...
自学web前端觉得好难,可能你遇到了这些困境
好多人跟我说上学的时候也学过前端,毕业了想从事web前端开发的工作,但自学起来好难,快要放弃了,所以我总结了一些大家遇到的困境,希望对你会有所帮助。 目录 1. 意志是否坚定 2. 没有找到合适自己的老师 3. 为了找…...
ASEMI中低压MOS管18N20参数,18N20封装,18N20尺寸
编辑-Z ASEMI中低压MOS管18N20参数: 型号:18N20 漏极-源极电压(VDS):200V 栅源电压(VGS):30V 漏极电流(ID):18A 功耗(PD&#x…...
[NetBackup]客户端安装后server无法连通client
client name处填写客户端主机名,server to use for backups and restores处填写server端名字,与hosts文件内保持一致;source client for restores处填写client主机名,与server端hosts文件中保持一致,与主机实际名称保持…...
黑马Java后端项目实战--在线聊天交友
【课程简介】 越来越多的系统都有消息推送的功能,如聊天室、邮件推送、系统消息推送等; 要实现消息推送就需要服务端在数据有变化时主动推送消息给客户端,本次课程将带大家使用websocket实现消息推送。 【主讲内容】 1.方法:如…...
【实战系列 2】Yapi接口管理平台Getshell-Linux后门权限维持与痕迹清除
文章目录 前言一、网站主页到Getshell二、SSH软链接后门三、Linux权限维持 --隐藏踪迹3.1 隐藏远程SSH登陆记录3.2、ssh软链接后门连接失败的原因以及解决办法3.3、隐藏踪迹-痕迹清楚3.3.1、隐藏历史操作命令3.3.2、隐藏文件/文件夹3.3.3、修改文件时间戳3.3.4、隐藏权限3.3.5、…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
