当前位置: 首页 > news >正文

Python面试宝典第4题:环形链表

题目

        给你一个链表的头节点 head ,判断链表中是否有环。如果存在环 ,则返回 true 。 否则,返回 false 。

        如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

        示例:

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

快慢指针法

        快慢指针法,也叫Floyd判圈法,是解决链表中环检测问题的经典算法。其核心思想是使用两个指针,一个快指针每次移动两个节点,一个慢指针每次移动一个节点。如果链表中存在环,快慢指针最终会在环中的某一点相遇。若不存在环,快指针会先到达链表尾部。使用快慢指针法求解本题的主要步骤如下。

        1、初始化指针。开始时,定义两个指针,一个快指针(fast)和一个慢指针(slow),均指向链表的头节点。

        2、移动指针。每次迭代时,慢指针(slow)向前移动一步,快指针(fast)向前移动两步。如果链表中存在环,由于快指针移动速度是慢指针的两倍,最终快指针会追上慢指针。

        3、终止条件。如果链表中没有环,快指针会首先到达链表的尾部(None),这时可以确定链表无环。相反,如果快慢指针相遇,则表明链表中存在环。

        根据上面的算法步骤,我们可以得出下面的示例代码。

class ListNode:def __init__(self, x):self.val = xself.next = Nonedef create_linked_list(length, pos = -1):if length < 1 or (pos != -1 and (pos < 0 or pos >= length)):return Nonehead = ListNode(0)current = headcycle_node = Nonefor i in range(1, length + 1):new_node = ListNode(i)current.next = new_nodecurrent = new_nodeif i == pos + 1:cycle_node = new_node# 只有当pos有效且不为-1时,才创建环if cycle_node:current.next = cycle_node# 返回真正的头节点,忽略初始的0节点return head.nextdef has_cycle_fast_slow_pointer(head):if head is None or head.next is None:return Falseslow = headfast = head.nextwhile fast is not None and fast.next is not None:if slow == fast:return Trueslow = slow.nextfast = fast.next.nextreturn False# 创建有环链表
head_with_cycle = create_linked_list(4, 1)
# 输出: True
print(has_cycle_fast_slow_pointer(head_with_cycle))# 创建无环链表
head_no_cycle = create_linked_list(4, -1)
# 输出: False
print(has_cycle_fast_slow_pointer(head_no_cycle))

哈希表法

        哈希表法利用数据结构中的哈希表来记录每个访问过的节点。由于哈希表的查找效率非常高,平均时间复杂度为O(1),故我们可以在遍历链表的同时,将每个访问过的节点添加到哈希表中。当发现某个节点已经被访问过,即该节点存在于哈希表中时,则可断定链表中存在环。使用哈希表法求解本题的主要步骤如下。

        1、初始化。创建一个空的哈希表,在Python中,通常是集合set。

        2、遍历链表。从链表头开始遍历,对于每一个访问到的节点,执行以下操作。

        (1)检查当前节点是否已经在哈希表中。

        (2)如果不在,将当前节点添加到哈希表中,并继续遍历下一个节点。

        (3)如果在哈希表中发现了当前节点,说明存在环,直接返回True。

        3、遍历结束。如果遍历完整个链表都没有发现重复的节点,则说明链表中没有环,返回False。

        根据上面的算法步骤,我们可以得出下面的示例代码。

def has_cycle_hashset(head):visited_nodes = set()while head is not None:# 如果节点已经在集合中,说明有环if head in visited_nodes:return Truevisited_nodes.add(head)head = head.next# 遍历结束,没有发现环return False# 创建有环链表
head_with_cycle = create_linked_list(4, 1)
# 输出: True
print(has_cycle_hashset(head_with_cycle))# 创建无环链表
head_no_cycle = create_linked_list(4, -1)
# 输出: False
print(has_cycle_hashset(head_no_cycle))

总结

        快慢指针法不需要额外的空间,时间复杂度为O(n),其中n是链表中的节点数量。哈希表法则提供了另一种思路,虽然它需要额外的O(n)空间,但优点是实现直观,易于理解和编码。

        在实际应用中,如果对空间复杂度有严格要求,推荐使用快慢指针法。如果空间不是问题,而对代码的简洁性和直观性有更高要求,哈希表法也是一个不错的选择。

💡 如果想阅读最新的文章,或者有技术问题需要交流和沟通,可搜索并关注微信公众号“希望睿智”。

相关文章:

Python面试宝典第4题:环形链表

题目 给你一个链表的头节点 head &#xff0c;判断链表中是否有环。如果存在环 &#xff0c;则返回 true 。 否则&#xff0c;返回 false 。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xf…...

Kubernetes (K8s) 底层原理

Kubernetes (K8s) 的底层原理涉及多个关键组件和概念&#xff0c;确保容器化应用程序的自动化部署、扩展和管理。以下是 Kubernetes 的底层原理及其关键组件的详细描述。 核心组件 Etcd 功能&#xff1a;分布式键值存储&#xff0c;用于存储集群的所有数据&#xff0c;包括配置…...

解析Kotlin中的委托(包括类委托,属性委托)【笔记摘要】

1.委托模式 委托模式&#xff1a;操作对象不会去处理某段逻辑&#xff0c;而是会把工作委托给另外一个辅助对象去处理。 例如我们要设计一个自定义类的来实现Set&#xff0c;可以将该实现委托给另一个对象&#xff1a; class MySet<T> (val helperSet: HashSet<T>…...

vue3+ts+uniapp+vite+pinia项目配置

开发环境&#xff1a; node >18&#xff0c;npm >8.10.2&#xff0c;vue < 3.2.31 安装项目 npx degit dcloudio/uni-preset-vue#vite-ts vue3-uniapp 1、引入样式规范 npm add -D eslint eslint-config-airbnb-base eslint-config-prettier eslint-import-resolv…...

大数据开发语言 Scala(四):面向对象编程

目录 1. 概述 2. 面向对象编程的基本概念 2.1 类和对象 2.2 继承和多态 2.3 封装和访问控制 3. 面向对象编程在大数据开发中的应用 3.1 Spark中的面向对象编程 3.2 面向对象编程在数据清洗和预处理中 3.3 面向对象编程在机器学习中的应用 4. 面向对象编程的高级特性 …...

C++ //练习 14.31 我们的StrBlobPtr类没有定义拷贝构造函数、赋值运算符及析构函数,为什么?

C Primer&#xff08;第5版&#xff09; 练习 14.31 练习 14.31 我们的StrBlobPtr类没有定义拷贝构造函数、赋值运算符及析构函数&#xff0c;为什么&#xff1f; 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#xff1a;vim 解释&#xff1a; 因为…...

通配符和正则表达式之间的关系

通配符和正则表达式&#xff08;正则&#xff09;都是用于匹配字符串的工具&#xff0c;但它们的复杂性和用途有所不同。下面是它们之间的主要关系和区别&#xff1a; 通配符 通配符主要用于简单的模式匹配&#xff0c;常见于文件系统操作中&#xff0c;例如在命令行中查找文…...

GY-30光照传感器软件I2C方式驱动代码,基于STM32Cube

GY-30光照传感器的具体资料可以去淘宝搜索然后问卖家要&#xff0c;网上也有&#xff0c;所以这里我就不多嘴了。 VCC连接3到5伏电压&#xff0c;根据文件开头的描述在STM32CubeMX中配置好外设。 STM32Cube开发方式就是4个字“简单直接”&#xff0c;直接上代码。 gy30.h #…...

双相元编程:一种新语言设计方法

本文讨论了编程语言的一种趋势&#xff0c;即允许相同的语法表达 在两个不同阶段或环境&#xff08;上下文&#xff09;中执行的计算同时保持跨阶段&#xff08;上下文&#xff09;的一致行为。这些阶段通常在时间上&#xff08;运行时间&#xff09;或空间上&#xff08;运行…...

基于SpringBoot校园外卖配送系统设计和实现(源码+LW+调试文档+讲解等)

&#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN作者、博客专家、全栈领域优质创作者&#xff0c;博客之星、平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f31f;文末获取源码数据库&#x1f31f; 感兴趣的可以先收藏起来&#xff0c;…...

茗鹤APS高级计划排程系统,在集团多工厂协同生产下的应用

随着业务规模的扩大和市场的全球化&#xff0c;越来越多的企业选择“总部多工厂基地”的模式&#xff0c;此种模式大幅提升企业的产能与产量&#xff0c;有效分散风险。然后&#xff0c;与之而来的是对企业的管理提出更高的管理要求。多个生产基地不仅面临集团下发的周期性计划…...

分享六款免费u盘数据恢复工具,U盘恢复工具集合【工具篇】

U盘里面的数据丢失了怎么找回&#xff1f;随着数字化时代的深入发展&#xff0c;U盘已成为我们日常生活中不可或缺的数据存储工具。然而&#xff0c;由于各种原因&#xff0c;如误删除、格式化、病毒攻击等&#xff0c;U盘中的数据可能会丢失&#xff0c;给用户带来极大的困扰。…...

Linux 的启动流程

第一步、加载内核 操作系统接管硬件以后&#xff0c;首先读入 /boot 目录下的内核文件。 以我的电脑为例&#xff0c;/boot 目录下面大概是这样一些文件&#xff1a; $ ls /bootconfig-3.2.0-3-amd64config-3.2.0-4-amd64grubinitrd.img-3.2.0-3-amd64initrd.img-3.2.0-4-amd6…...

思维导图插件--jsMind的使用

vue引入jsmind&#xff08;右键菜单&#xff09;_jsmind.menu.js-CSDN博客 第一版 vue-JsMind思维导图实现&#xff08;包含鼠标右键自定义菜单&#xff09;_jsmind 右键菜单-CSDN博客 // 新增节点addNode() {console.log(this.get_selected_nodeid());this.get_selected_…...

mac上使用finder时候,显示隐藏的文件或者文件夹

默认在finder中是不显示隐藏的文件和文件夹的&#xff0c;但是想创建.gitignore文件&#xff0c;并向里面写入内容&#xff0c;即便是打开xcode也是不显示这几个隐藏文件的&#xff0c;那有什么办法呢&#xff1f; 使用快捷键&#xff1a; 使用finder打开包含隐藏文件的文件夹…...

泰雷茲具有首个通过FIPS 140-3 三级认证的HSMs

泰雷兹LunaHsm是业界首款通过FIPS140-33级认证的解决方案&#xff0c;安策引进泰雷兹HSM产品可以帮助您满足您的数据安全合规性需求&#xff0c;阻力企业提高竞争力。 安策提供泰雷茲ThalesLunaHSMs成为首个通过FIPS140-3三级认证的硬件安全模块图 我们很高兴地宣布&#xff0c…...

美术馆预约小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;展品信息管理&#xff0c;管理员管理&#xff0c;用户管理&#xff0c;美术馆管理&#xff0c;基础数据管理&#xff0c;论坛管理 微信端账号功能包括&#xff1a;系统首页&#xff0c;美术馆&#xff…...

序列化Serializable

一、传输对象的方式 将对象从内存传输到磁盘进行保存&#xff0c;或者进行网络传输&#xff0c;有两种方式&#xff1a; 实现Serializable接口&#xff0c;直接传输对象转成json字符串后&#xff0c;进行字符串传输 二、直接传输对象 implements Serializable Data Equal…...

编写静态库

一、静态库 1.制作完成整体目录结构 2.首先创建mymath.c和mymath.h 3.编写Makefile 4.创建测试的main函数 test文件夹 先把lib移到test文件夹里面 4.编译链接 gcc main.c -I ./lib/include/ -L ./lib/mymathlib/ -l mymath 5.形成可执行程序a.out 要是不想执行第四步那么麻烦…...

hive的表操作

常用的hive命令 切换数据库use test;查询表的建表信息show create table 数据库名称.表名;查看表的类型信息desc formatted 数据库名称.表名; 删除内部表 drop table 数据库名称.表名; 先启动hdfs &#xff0c;mysql &#xff0c; hiveservice2&#xff0c;beeline CREATE [EX…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...