【LeetCode 算法】Linked List Cycle 环形链表
文章目录
- Linked List Cycle 环形链表
- 问题描述:
- 分析
- 代码
- 哈希
- 快慢指针
- Tag
Linked List Cycle 环形链表
问题描述:
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
链表中节点的数目范围是 [ 0 , 1 0 4 ] − 1 0 5 < = N o d e . v a l < = 1 0 5 p o s 为 − 1 或者链表中的一个有效索引 链表中节点的数目范围是 [0, 10^4]\\ -10^5 <= Node.val <= 10^5\\ pos 为 -1 或者链表中的一个 有效索引 链表中节点的数目范围是[0,104]−105<=Node.val<=105pos为−1或者链表中的一个有效索引
分析
目标就是判断链表中是否有环。
对于无环链表,依次遍历节点,最后一定是null,否则就会进入循环,之前已经访问过的节点,势必会重新访问。
所以如何知道节点是否被访问过,就是需要解决的问题。
错误
有的思路是利用节点的值,进行判断,很明显这个思路有缺陷,如果整个链表都是相同的值,就明显无法进行判断。
哈希
而使用哈希表,就可以解决这个问题,它可以保证哈希表中的元素一定是唯一的,不会重复。
这个原理可以自行Bing,GPT什么的。
所以遍历的过程中,每遇到一个新节点,就利用哈希表进行判断是否出现过,如果出现过,说明了节点一定重复访问了,从而说明 有环。
时间复杂度 O ( N ) O(N) O(N) ,空间复杂度 O ( N ) O(N) O(N)
这个是比较常规的操作,也是大部分的思路。
升级
这个思路很典型,但是随着数据规模的增加,时空的消耗也会增加。
快慢指针
另一种是双指针,一个fast,一个slow,fast一次走2步,slow一次一步。
就像围着操场[环]跑步,fast一定会追上slow.
其实这里的双指针也叫快慢指针,该思路还可以解决链表的其他问题。
时间复杂度 O ( N ) O(N) O(N)
空间复杂度 O ( 1 ) O(1) O(1)
代码
哈希
public boolean hasCycle(ListNode head) {Set<ListNode> seen = new HashSet<ListNode>();while (head != null) {if (!seen.add(head)) {return true;}head = head.next;}return false;}
时间复杂度 O ( N ) O(N) O(N)
空间复杂度 O ( N ) O(N) O(N)
快慢指针
public boolean hasCycle(ListNode head) {if(head==null||head.next==null) return false;ListNode vh = new ListNode(-1);vh.next = head;ListNode fast = head.next,slow = vh;while(fast!=null&&fast.next!=null){if(fast==slow) return true;fast = fast.next.next;slow = slow.next;}return false;}
时间复杂度 O ( N ) O(N) O(N)
空间复杂度 O ( 1 ) O(1) O(1)
Tag
LinkedList
Hash
Two Pointers
相关文章:
【LeetCode 算法】Linked List Cycle 环形链表
文章目录 Linked List Cycle 环形链表问题描述:分析代码哈希快慢指针 Tag Linked List Cycle 环形链表 问题描述: 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达…...
RedHat7.9安装mysql8.0.32 ↝ 二进制方式
RedHat7.9安装mysql8.0.32 ↝ 二进制方式 一、rpm方式安装1、检查是否安装了mariadb2、下载mysqlmysql8.0.323、上传解压4、创建安装目录,拷贝解压后的文件至安装目录/usr/local/mysql8.0/5、创建相关目录,开始安装6、创建mysql组和用户7、更改安装目录归…...
数据库面试题题
题干: -- 子查询 CREATE TABLE emp( empno INT, ename VARCHAR(50), job VARCHAR(50), mgr INT, hiredate DATE, sal DECIMAL(7,2), comm DECIMAL(7,2), deptno INT ) ; INSE…...
瑞吉外卖项目 基于spring Boot+mybatis-plus开发 超详细笔记,有源码链接
源码地址:https://gitee.com/programmer-xiao-kai/reggie_tack_out 前置知识: Java基础知识Java Web vueSpring BootSSMMaven 软件开发流程 角色分工 项目经理:对整个项目负责,任务分配、把控进度产品经理:进行需求调研,输出需…...
Redis Cluster 在Spring中遇到的问题
Redis集群配置可能会在运行时更改。可以添加新节点,可以更改特定插槽的主节点。还有可能因为master宕机或网络抖动等原因,引起了主从切换。 无法感知集群槽位变化 SpringBoot2.x 开始默认使用的 Redis 客户端由 Jedis 变成了 Lettuce,但是当…...
linux远程桌面管理工具 xrdp
Xrdp 是一个微软远程桌面协议(RDP)的开源实现,它允许你通过图形界面控制远程系统。通过 RDP,你可以登录远程机器,并且创建一个真实的桌面会话,就像你登录本地机器一样。 如何在Ubuntu 20.04 上安装 Xrdp 服…...
硬件-8-操作系统的历史
操作系统的最强入门科普(Unix/Linux篇) 操作系统的发展史(DOS/Windows篇) Mac操作系统进化史 手机操作系统的沉浮往事(上) 手机操作系统的沉浮往事(下) 1 操作系统种类 我们天天都…...
self.register_buffer()中的值发生变化
PyTorch中定义模型时,有时候会遇到self.register_buffer(name, Tensor)的操作,该方法的作用是定义一组参数,该组参数的特别之处在于:模型训练时不会更新(即调用 optimizer.step() 后该组参数不会变化,只可人…...
[Tools: Pycharm] Bug合集
1. Debug mode:Pycharm不显示变量值(Unable to display frame variables);在python console中交互不输出值 选择Gevent compatible:File > Settings > Build, Execution, Deployment > Python Debugger >…...
【JAVASE】循环结构
⭐ 作者:小胡_不糊涂 🌱 作者主页:小胡_不糊涂的个人主页 📀 收录专栏:浅谈Java 💖 持续更文,关注博主少走弯路,谢谢大家支持 💖 循环 1. 循环结构1.1 while 循环1.2 bre…...
NoSQL之Redis配置使用
目录 一、关系数据库与非关系型数据库 1.1.关系型数据库的概述 1.2关系型数据库的优缺点 1.2.1优点 1.2.2缺点 1.3.非关系型数据库的概述 二.关系数据库与非关系型数据库的区别 2.1数据存储方式不同 2.2扩展方式不同 2.3对事务性的支持不同 2.4非关系型数据库产生背景 2…...
Ansible最佳实践之Playbook使用过滤器处理网络地址
写在前面 使用过滤器检查、验证和操作包含网络信息的变量理解不足小伙伴帮忙指正 傍晚时分,你坐在屋檐下,看着天慢慢地黑下去,心里寂寞而凄凉,感到自己的生命被剥夺了。当时我是个年轻人,但我害怕这样生活下去…...
测试常见前端bug
目录 协作 测试方法 标签:标签 内容/ref/ 判断 arr&&arr.length 交互 样式不生效:devtools查找,编译前的标签,运行时不一定存在 可交互的需要提示 hover样式 没有交互逻辑,就不要设置交互 无法交互…...
【Python数据分析】Python常用内置函数(一)
🎉欢迎来到Python专栏~Python常用内置函数(一) ☆* o(≧▽≦)o *☆嗨~我是小夏与酒🍹 ✨博客主页:小夏与酒的博客 🎈该系列文章专栏:Python学习专栏 文章作者技术和水平有限,如果文…...
OpenCV图像处理-图像分割-MeanShift
MeanShift 1. 基本概念2.代码示例 1. 基本概念 MeanShift严格说来并不是用来对图像进行分割的,而是在色彩层面的平滑滤波。它会中和色彩分布相近的颜色,平滑色彩细节,侵蚀掉面积较小的的颜色区域,它以图像上任意一点P为圆心&…...
【Rust 基础篇】Rust Trait 实现:灵活的接口抽象
导言 Rust是一种以安全性和高效性著称的系统级编程语言,其设计哲学是在不损失性能的前提下,保障代码的内存安全和线程安全。为了实现这一目标,Rust引入了"所有权系统"、"借用检查器"等特性,有效地避免了常见…...
【嵌入式Linux项目】基于Linux的全志H616开发板智能家居项目(语音控制、人脸识别、安卓APP和PC端QT客户端远程操控)有视频功能展示
目录 一、功能需求 二、开发环境 1、硬件: 2、软件: 3、引脚分配: 三、关键点 1、设计模式之工厂模式 2、wiringPi库下的相关硬件操作函数调用 3、语音模块的串口通信 4、线程 5、摄像头的实时监控和拍照功能 6、人脸识别 四、编…...
ElasticSearch基础篇-条件查询与映射
ElasticSearch基础篇二 条件查询 GET http://10.192.193.98:9200/shopping/_search?qtitle:小米手机q:代表查询条件 响应结果 {"took": 772,"timed_out": false,"_shards": {"total": 1,"successful": 1,"skipped…...
大模型部署框架 FastLLM 实现细节解析
0x0. 前言 接着 大模型部署框架 FastLLM 简要解析 这篇文章首先梳理了一下FastLLM的调用链和关键的数据结构,然后解析了 FastLLM 的一些实现细节和CPU/GPU后端实现采用的优化技巧。 0x1. 调用链和数据结构解析 以chatglm-6b的支持为例,函数入口在 htt…...
Flutter ios真机调试连接断开后应用闪退
使用ios真机调试的时候,能正常打开应用,但是当数据线断开连接的时候,应用就会关闭,重新打开就会闪退。 原因是flutter默认在开发过程中使用debug模式编译 只需要将debug选择为release 重新编译就行。...
别只盯着协议!用TC8测试案例深度解读车载网络中的ARP与ICMP:安全与稳定的隐藏关卡
车载以太网底层协议实战:从TC8测试案例看ARP与ICMP的安全设计 当一辆现代汽车以100km/h行驶时,其车载网络每秒需要处理超过5000条网络报文。这些报文中的绝大多数,都由ARP和ICMP这样的基础协议承载。在传统IT领域被视为"简单"的协议…...
从旅游Vlog到新闻视频:QVHIGHLIGHTS数据集在跨领域应用中的实战指南
QVHIGHLIGHTS数据集:跨领域视频内容智能解析的工程实践 当你在旅行Vlog中搜索"日落时分的海滩漫步",或在新闻视频中寻找"抗议活动现场冲突画面",传统视频平台只能返回整段视频——这就像给你一整本书而不是精确的页码。Q…...
嘉立创PCB打样被加价到170元?手把手教你用STM32H743飞控板案例解决‘拆单嫌疑’
STM32H743飞控板PCB打样避坑指南:如何巧妙应对嘉立创拆单判定 最近不少硬件开发者在使用嘉立创进行STM32H743飞控板PCB打样时,遇到了一个令人头疼的问题——原本33元的4层板打样价格突然飙升到170多元。这种情况往往是由于平台算法误判设计文件存在"…...
Arcgis符号化实战:用矢量文件制作专业级统计地图(附最新配色方案)
ArcGIS符号化实战:用矢量文件制作专业级统计地图(附最新配色方案) 当你面对一叠枯燥的表格数据时,是否想过如何让这些数字"活"起来?统计地图正是将抽象数据转化为直观视觉表达的利器。作为地理信息系统领域的…...
OBS多平台直播同步解决方案:从配置到优化的完整指南
OBS多平台直播同步解决方案:从配置到优化的完整指南 【免费下载链接】obs-multi-rtmp OBS複数サイト同時配信プラグイン 项目地址: https://gitcode.com/gh_mirrors/ob/obs-multi-rtmp 在当今内容创作领域,多平台同步直播已成为扩大受众覆盖的关键…...
QT6.5串口编程第一步:用CMakeLists.txt引入SerialPort模块的避坑指南
QT6.5串口编程避坑指南:CMakeLists.txt配置全解析 当你满怀期待地在QT6.5项目中引入串口通信功能,却在编译时遭遇"找不到QtSerialPort"的红色错误提示,这种挫败感我深有体会。作为一位经历过无数次类似"战斗"的开发者&am…...
IEEE会议论文避雷指南:如何用GSview+Photoshop搞定EPS图片压缩与特殊字符命名
IEEE会议论文图片处理全攻略:从格式转换到命名规范 第一次投稿IEEE会议的新手研究者们,往往会在图片处理环节栽跟头——明明内容扎实、实验充分,却因为技术细节问题被编辑退回修改。这不是学术能力的问题,而是对印刷出版标准的不熟…...
从零构建高校智慧校园网:VLAN+MSTP+VRRP黄金组合实战解析
高校智慧校园网实战:VLANMSTPVRRP黄金架构深度解析 1. 智慧校园网络架构设计新思维 在数字化校园建设浪潮中,网络基础设施正面临前所未有的挑战。某985高校的IT部门最近做过统计:平均每间教室需要承载36台终端设备(含IoT设备&…...
告别UnsatisfiedLinkError!OpenCV Java版环境配置的终极避坑指南(含Maven/Gradle依赖)
告别UnsatisfiedLinkError!OpenCV Java版环境配置的终极避坑指南(含Maven/Gradle依赖) 在计算机视觉领域,OpenCV无疑是开发者最常用的工具库之一。然而,当Java开发者满怀期待地引入OpenCV依赖后,却常常被U…...
nlp_gte_sentence-embedding_chinese-large保姆级教程:免配置镜像启动+Web界面使用详解
nlp_gte_sentence-embedding_chinese-large保姆级教程:免配置镜像启动Web界面使用详解 你是不是经常遇到这样的问题:手里有一堆文档,想快速找到和某个问题最相关的内容,却只能靠关键词搜索,结果要么漏掉,要…...
