当前位置: 首页 > 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…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...

Qt的学习(一)

1.什么是Qt Qt特指用来进行桌面应用开发&#xff08;电脑上写的程序&#xff09;涉及到的一套技术Qt无法开发网页前端&#xff0c;也不能开发移动应用。 客户端开发的重要任务&#xff1a;编写和用户交互的界面。一般来说和用户交互的界面&#xff0c;有两种典型风格&…...

数据库——redis

一、Redis 介绍 1. 概述 Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的、高性能的内存键值数据库系统&#xff0c;具有以下核心特点&#xff1a; 内存存储架构&#xff1a;数据主要存储在内存中&#xff0c;提供微秒级的读写响应 多数据结构支持&…...