【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 重新编译就行。...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...
windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...
使用SSE解决获取状态不一致问题
使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件,这个上传文件是整体功能的一部分,文件在上传的过程中…...
前端高频面试题2:浏览器/计算机网络
本专栏相关链接 前端高频面试题1:HTML/CSS 前端高频面试题2:浏览器/计算机网络 前端高频面试题3:JavaScript 1.什么是强缓存、协商缓存? 强缓存: 当浏览器请求资源时,首先检查本地缓存是否命中。如果命…...
表单设计器拖拽对象时添加属性
背景:因为项目需要。自写设计器。遇到的坑在此记录 使用的拖拽组件时vuedraggable。下面放上局部示例截图。 坑1。draggable标签在拖拽时可以获取到被拖拽的对象属性定义 要使用 :clone, 而不是clone。我想应该是因为draggable标签比较特。另外在使用**:clone时要将…...
工厂方法模式和抽象工厂方法模式的battle
1.案例直接上手 在这个案例里面,我们会实现这个普通的工厂方法,并且对比这个普通工厂方法和我们直接创建对象的差别在哪里,为什么需要一个工厂: 下面的这个是我们的这个案例里面涉及到的接口和对应的实现类: 两个发…...
