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、…...
Phi-3-Mini-128K企业级应用:基于MCP协议构建安全可控的AI工具链
Phi-3-Mini-128K企业级应用:基于MCP协议构建安全可控的AI工具链 最近和几个在企业里做技术管理的朋友聊天,大家不约而同地提到了同一个烦恼:看着外面各种AI模型能力越来越强,心里痒痒的,真想引入到自己的业务流程里&a…...
QLVideo终极指南:让macOS Finder完美预览所有视频格式
QLVideo终极指南:让macOS Finder完美预览所有视频格式 【免费下载链接】QuickLookVideo This package allows macOS Finder to display thumbnails, static QuickLook previews, cover art and metadata for most types of video files. 项目地址: https://gitcod…...
DownKyi架构深度解析:高效B站视频下载工具的技术实现与实战指南
DownKyi架构深度解析:高效B站视频下载工具的技术实现与实战指南 【免费下载链接】downkyi 哔哩下载姬downkyi,哔哩哔哩网站视频下载工具,支持批量下载,支持8K、HDR、杜比视界,提供工具箱(音视频提取、去水印…...
SEO_避开这些常见误区,让你的SEO效果翻倍
<h2>避开这些常见误区,让你的SEO效果翻倍</h2> <p>在当今的互联网时代,搜索引擎优化(SEO)已经成为了每个网站和博客运营者必须掌握的技能之一。许多人在进行SEO时却会犯一些常见的错误,这些错误不仅…...
7_Harness驾驭工程安全与成本层:DevSecOps与云成本优化
7_Harness驾驭工程安全与成本层:DevSecOps与云成本优化 关键字: DevSecOps、安全测试编排、STO、SAST、DAST、SCA、OPA策略、策略即代码、Rego、软件供应链安全、SBOM、依赖追溯、云成本管理、CCM、FinOps、资源浪费识别、预算告警、RBAC、审计日志、单位…...
Phi-4-Reasoning-VisionGPU算力:双卡4090推理吞吐达12 token/s实测
Phi-4-Reasoning-VisionGPU算力:双卡4090推理吞吐达12 token/s实测 1. 项目概述 Phi-4-Reasoning-Vision是一款基于微软Phi-4-reasoning-vision-15B多模态大模型开发的高性能推理工具。该工具专为双卡RTX 4090环境优化,通过精心设计的架构和优化策略&a…...
保姆级教程:在银河麒麟V10桌面版上,用Docker容器化部署SpringBoot + 达梦数据库应用
银河麒麟V10桌面版容器化实战:SpringBoot与达梦数据库的Docker化部署指南 在国产化技术栈日益成熟的今天,将传统应用迁移到容器化环境已成为提升部署效率和系统可移植性的关键路径。银河麒麟V10作为国产操作系统的代表,结合飞腾CPU的硬件生态…...
基于Matlab的转子系统临界转速与主振型求解:传递矩阵法及其参数涉及等截面、材料与轮盘参数的...
140.基于matlab的求解转子系统前三个临界转速和主振型的传递矩阵法转子系统的不平衡响应 参数涉及等截面参数、材料参数、轮盘参数 程序已调通,可直接运行传递矩阵法这玩意儿在转子动力学里属于实操性极强的工具,今天咱们就拿Matlab直接开搞转子系统的前…...
HP-Socket创新项目原型迭代记录:变更、原因与效果
HP-Socket创新项目原型迭代记录:变更、原因与效果 【免费下载链接】HP-Socket High Performance TCP/UDP/HTTP Communication Component 项目地址: https://gitcode.com/gh_mirrors/hp/HP-Socket HP-Socket作为一款高性能TCP/UDP/HTTP通信组件,其…...
终极PrimeVue Toast组件交互事件回调指南:从基础到高级应用
终极PrimeVue Toast组件交互事件回调指南:从基础到高级应用 【免费下载链接】primevue Next Generation Vue UI Component Library 项目地址: https://gitcode.com/GitHub_Trending/pr/primevue PrimeVue是一款功能强大的Vue UI组件库,其中Toast组…...
