LeetCode 热题100 141. 环形链表
LeetCode 热题100 | 141. 环形链表
大家好,今天我们来解决一道经典的算法题——环形链表。这道题在 LeetCode 上被标记为简单难度,要求我们判断一个链表中是否存在环。下面我将详细讲解解题思路,并附上 Python 代码实现。
题目描述
给定一个链表的头节点 head,判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达,则链表中存在环。返回 true 表示链表中有环,否则返回 false。
示例:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
解题思路
判断链表是否有环,常用的方法是 快慢指针法(Floyd 判圈算法)。快慢指针法的核心思想是使用两个指针,一个快指针和一个慢指针,快指针每次走两步,慢指针每次走一步。如果链表中有环,快指针最终会追上慢指针;如果没有环,快指针会到达链表末尾。
核心思想
- 快慢指针:
- 初始化两个指针
slow和fast,都指向链表的头节点head。 slow每次移动一步,fast每次移动两步。- 如果
fast或fast.next为None,说明链表没有环。 - 如果
slow和fast相遇,说明链表有环。
- 初始化两个指针
代码实现
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef hasCycle(head):""":type head: ListNode:rtype: bool"""if not head or not head.next:return Falseslow = head # 慢指针fast = head # 快指针while fast and fast.next:slow = slow.next # 慢指针走一步fast = fast.next.next # 快指针走两步if slow == fast: # 如果相遇,说明有环return Truereturn False # 如果没有相遇,说明无环
代码解析
-
初始化:
- 如果链表为空或只有一个节点,直接返回
False,因为不可能有环。 - 初始化两个指针
slow和fast,都指向链表的头节点head。
- 如果链表为空或只有一个节点,直接返回
-
遍历链表:
- 使用
while循环遍历链表,直到fast或fast.next为None。 slow每次移动一步,fast每次移动两步。- 如果
slow和fast相遇,说明链表有环,返回True。
- 使用
-
返回结果:
- 如果遍历结束后没有相遇,说明链表无环,返回
False。
- 如果遍历结束后没有相遇,说明链表无环,返回
复杂度分析
- 时间复杂度:O(n),其中 n 是链表的节点数。快指针最多遍历链表两次。
- 空间复杂度:O(1),只使用了常数个额外空间。
示例运行
示例 1
# 创建链表 [3,2,0,-4],并形成环
head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(0)
head.next.next.next = ListNode(-4)
head.next.next.next.next = head.next # 形成环# 判断链表是否有环
print(hasCycle(head)) # 输出: True
示例 2
# 创建链表 [1,2],并形成环
head = ListNode(1)
head.next = ListNode(2)
head.next.next = head # 形成环# 判断链表是否有环
print(hasCycle(head)) # 输出: True
示例 3
# 创建链表 [1],无环
head = ListNode(1)# 判断链表是否有环
print(hasCycle(head)) # 输出: False
总结
通过快慢指针法,我们可以高效地判断链表是否有环。这种方法的时间复杂度为 O(n),空间复杂度为 O(1),能够处理较大的输入规模。希望这篇题解对你有帮助!如果还有其他问题,欢迎继续提问!
关注我,获取更多算法题解和编程技巧!
相关文章:
LeetCode 热题100 141. 环形链表
LeetCode 热题100 | 141. 环形链表 大家好,今天我们来解决一道经典的算法题——环形链表。这道题在 LeetCode 上被标记为简单难度,要求我们判断一个链表中是否存在环。下面我将详细讲解解题思路,并附上 Python 代码实现。 题目描述 给定一个…...
以绘图(绘制点、直线、圆、椭圆、多段线)为例子 通过设计模式中的命令模式实现
为了在命令模式的基础上实现撤销(Undo)和回退(Redo)功能,我们可以在每个命令类中记录一些必要的状态,允许我们撤销之前的操作,并在需要时回退操作。常见的做法是使用一个命令堆栈来存储历史命令…...
鹏哥c语言数组(初阶数组)
前言: 对应c语言视频54集 内容: 一维数组的创建 数组是一组相同元素的集合, 数组的创建方式 type_t就是数组的元素类型,const_n是一个常量表达式,用来指定数组的大小 c99标准之前的,数组的大小必须是…...
利用go-migrate实现MySQL和ClickHouse的数据库迁移
1. 背景 在使用gorm时 , 尽管已经有了自动建表和钩子函数 . 但是在面临希望了解到数据库的变更 , 和插入一些系统字段时 , 以及最关键的数据库迁移的工作 . gorm显得稍微有点不便 . 在了解到migrate这项技术后 , 就使用go-migrate开发了一个可以迁移MySQL和ClickHouse数据库的…...
计算机毕业设计SpringBoot+Vue.js企业客户管理系统(源码+LW文档+PPT+讲解+开题报告)
温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 作者简介:Java领…...
jmeter 如何做移动端的测试 特别是兼容性测试
JMeter本身主要是一款用于性能测试和功能测试的工具,虽然它并非专门为移动端测试设计,但可以通过一些方式来对移动端应用进行测试,以下从测试准备、测试过程及注意事项等方面为你详细介绍: 一、测试准备 (一)环境搭建 JMeter安装与配置:确保JMeter已经正确安装在测试机…...
深度学习技术全景图:从基础架构到工业落地的超级进化指南
🔍 目录导航 基础架构革命训练优化秘技未来战场前瞻 🧩 一、基础架构革命 1.1 前馈神经网络(FNN) ▍核心结构 import torch.nn as nnclass FNN(nn.Module):def __init__(self):super().__init__()self.fc1 nn.Linear(784, 25…...
vllm部署LLM(qwen2.5,llama,deepseek)
目录 环境 qwen2.5-1.5b-instruct 模型下载 vllm 安装 验证安装 vllm 启动 查看当前模型列表 OpenAI Completions API(文本生成) OpenAI Chat Completions API(chat 对话) vllm 进程查看,kill llama3 deep…...
基于SpringBoot的“古城景区管理系统”的设计与实现(源码+数据库+文档+PPT)
基于SpringBoot的“古城景区管理系统”的设计与实现(源码数据库文档PPT) 开发语言:Java 数据库:MySQL 技术:SpringBoot 工具:IDEA/Ecilpse、Navicat、Maven 系统展示 系统整体功能图 系统首页界面 系统注册界面 景…...
如何防止 Docker 注入了恶意脚本
根据您的描述,攻击者通过 CentOS 7 系统中的 Docker 注入了恶意脚本,导致自动启动名为 “masscan” 和 “x86botnigletjsw” 的进程。这些进程可能用于网络扫描或其他恶意活动。为了解决这一问题,建议您采取以下步骤: 1. 停止并删…...
使用python接入腾讯云DeepSeek
本文主要从提供SSE方式接入DeepSeek,并通过fastapi websocket对外提供接入方法。 参考文档: 腾讯云大模型:https://cloud.tencent.com/document/product/1759/109380 fastAPI官网:https://fastapi.tiangolo.com/ WebSocketManager…...
【MySQL】服务正在启动或停止中,请稍候片刻后再试一次【解决方案】
问题呈现 在使用MySQL的过程中我们可能会遇到以上的情况 解决方法 首先以管理员身份打开命令行窗口,注意是管理员身份,不然无权限访问。输入命令tasklist| findstr "mysql",用于查找mysql的残留进程。这个时候我们就会看到一个…...
测试工程师玩转DeepSeek之Prompt
以下是测试工程师使用DeepSeek的必知必会提示词指南,分为核心场景和高效技巧两大维度: 一、基础操作提示模板 1. 测试用例生成 "作为[金融系统/物联网设备/云服务]测试专家,请为[具体功能模块]设计测试用例,要求࿱…...
【PyTorch】2024保姆级安装教程-Python-(CPU+GPU详细完整版)-
一、准备工作 pytorch需要python3.6及以上的python版本 我是利用Anaconda来管理我的python。可自行安装Anaconda。 Anaconda官网 Free Download | Anaconda 具体Anaconda安装教程可参考 https://blog.csdn.net/weixin_43412762/article/details/129599741?fromshareblogdet…...
精选案例展 | 智己汽车—全栈可观测驱动智能化运营与成本优化
本案例为“观测先锋 2024 可观测平台创新应用案例大赛”精选案例,同时荣获IT168“2024技术卓越奖评选-年度创新解决方案”奖。 项目背景 近年来,中国汽车行业进入转型升级阶段,智能网联技术成为行业发展的核心。车联网、自动驾驶等技术的加速…...
MySQL 使用 `WHERE` 子句时 `COUNT(*)`、`COUNT(1)` 和 `COUNT(column)` 的区别解析
文章目录 1. COUNT() 函数的基本作用2. COUNT(*)、COUNT(1) 和 COUNT(column) 的详细对比2.1 COUNT(*) —— 统计所有符合条件的行2.2 COUNT(1) —— 统计所有符合条件的行2.3 COUNT(column) —— 统计某一列非 NULL 的记录数 3. 性能对比3.1 EXPLAIN 分析 4. 哪种方式更好&…...
Linux运维——网络管理
Linux网络管理 一、Linux网络应用要点二、命令常见用法2.1、curl2.1.1、发送GET请求2.1.2、发送POST请求2.1.3、设置请求头2.1.4、处理cookies2.1.5、处理重定向2.1.6、调试和详细信息2.1.7、使用代理2.1.8、文件上传2.1.9、其它常用选项2.1.10、综合示例 2.2、wget2.2.1、基本…...
STM32CUBEIDE FreeRTOS操作教程(十三):task api 任务访问函数
STM32CUBEIDE FreeRTOS操作教程(十三):task api 任务访问函数 STM32CUBE开发环境集成了STM32 HAL库进行FreeRTOS配置和开发的组件,不需要用户自己进行FreeRTOS的移植。这里介绍最简化的用户操作类应用教程。以STM32F401RCT6开发板…...
Jmeter+Jenkins接口压力测试持续集成
项目介绍 接口功能测试应用: http://www.weather.com.cn/data/cityinfo/<city_code>.html 测试功能:获取对应城市的天气预报 请求方法:Get 压测脚本开发工具:jmeter 源码脚本位置: https://github.com/shife…...
深入浅出ES6:现代JavaScript的基石
ES6(ECMAScript 2015)是JavaScript语言的一次重大更新,引入了许多新特性,使JavaScript更加强大、优雅和易于维护。这些特性已经成为现代JavaScript开发的基石,掌握它们对于任何JavaScript开发者都至关重要。本文将深入…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...
spring Security对RBAC及其ABAC的支持使用
RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型,它将权限分配给角色,再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...
aardio 自动识别验证码输入
技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”,于是尝试整合图像识别与网页自动化技术,完成了这套模拟登录流程。核心思路是:截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...
6.计算机网络核心知识点精要手册
计算机网络核心知识点精要手册 1.协议基础篇 网络协议三要素 语法:数据与控制信息的结构或格式,如同语言中的语法规则语义:控制信息的具体含义和响应方式,规定通信双方"说什么"同步:事件执行的顺序与时序…...
无需布线的革命:电力载波技术赋能楼宇自控系统-亚川科技
无需布线的革命:电力载波技术赋能楼宇自控系统 在楼宇自动化领域,传统控制系统依赖复杂的专用通信线路,不仅施工成本高昂,后期维护和扩展也极为不便。电力载波技术(PLC)的突破性应用,彻底改变了…...
