判断单链表是否有环?中点如何判断?入环点如何判断?

简介: 判断单链表是否有环?中点如何判断?入环点如何判断?

首先我们需要克服我们一种错误的认知,链表有环,并不是有“死节”,如下所示,左侧的这种链表结构是不存在的,因为在相交的那个节点不可能有两个指针,只有像右侧这种结构才是存在的

判断链表是否有环的方法:

第一种使用哈希表,在遍历的过程中将节点存入哈希表,如果发现某个节点在表中已经存在了,那么这个链表就是有环的,并且这个节点就是入环节点


第二种方法叫做Floyd判圈算法,或者是龟兔赛跑算法,其实就是快慢指针思想,算法流程如下所示:


使slow和fast这两个指针都指向链表的头部,slow指针每次走一步,fast指针每次走两步

由于fast指针走得快,如果链表有环,那么在移动的过程中,fast指针一定能在后面超越slow指针。如下所示:

如果链表有环,这两个指针一定能在某次移动之后相遇。如下所示:

我们可对该方法进行验证:

状态1:

如果在超越之前,fast落后slow一步,那么在下次移动的时候,fast走两步,slow走一步,两个指针就此相遇,如下所示:

状态2:

如果在超越之前,fast落后slow两步,那么在下次移动之后,fast走两步,slow走一步,又变成了状态1

以此类推,fast落后三步的时候,fast走两步,slow走一步,又可以变成状态2

因此我们可以得出如果链表有环,那么快慢指针就一定能够在某次移动后相遇

寻找链表的中点:

我们可以设置两个指针,快指针每次走两步,慢指针每次走一步,快指针走完整条链表时,慢指针指向的节点就是链表的中点

寻找链表的倒数第K个节点:

设置p1和p2两个指针,让p2指针先走K-1步

然后两个指针每次都走一步,p2指针走完链表后,p1指针指向的节点就是倒数第k个节点

寻找链表的入环点:

如下所示设置两个指针slow和fast,

快指针每次走两步,慢指针每次走一步

如果快慢指针能相遇,那么说明链表有环

快慢指针相遇之后,让快指针重新回到头节点,然后让快慢指针每次都只走一步,两个指针肯定能在某次移动之后再次相遇,这个相遇的节点,就是环形链表的入环点

fast指针每次移动3步是否可行?4步?5步?

是可行的,但可能会导致遍历的步数较多,并且可能会导致快指针直接跳过慢指针无法检测到环。所以,一般情况下,推荐使用快指针每次移动2步,慢指针每次移动1步的方式来判断链表是否有环。

相关文章
|
存储 网络协议 安全
Linux 在线/离线安装 NFS 服务及使用
-m 表示指定文件所在的文件系统或者块设备(处于 mount 状态)。所有访问该文件系统的进程都被列出。如上所示,有两个进程占用了,将其kill掉,再重新取消挂载。
3462 0
Linux 在线/离线安装 NFS 服务及使用
|
4月前
|
人工智能 前端开发 API
如何快速开发视频下载器
本文介绍如何基于开源工具yt-dlp开发功能全面的视频下载器网站。yt-dlp作为youtube-dl的增强版,支持1000+网站,具备高效下载、格式选择及字幕处理等特性。文章详细解析了前后端架构设计,包括简洁的前端界面与基于Flask/Django的后端API实现,封装yt-dlp核心功能,提供进度跟踪和文件管理。同时探讨容器化部署、性能优化及扩展功能(如字幕翻译、批量下载)。案例“AI易视频”展示了AI辅助开发的高效性。开发时需遵守法律,尊重版权。
|
算法
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
|
10月前
|
人工智能 算法 物联网
企业级RAG全链路优化关键技术
本文深入解析了企业级RAG全链路的关键技术、效果优化、性能优化及应用实践。
862 7
|
Docker 容器
docker ps --no-trunc 与 docker ps
docker ps --no-trunc 与 docker ps
214 1
|
SQL 关系型数据库 数据库
C语言与数据库:使用C语言操作SQLite等数据库。
C语言与数据库:使用C语言操作SQLite等数据库。
|
消息中间件 负载均衡 Kafka
Kafka学习---消费者(分区消费、分区平衡策略、offset、漏消费和重复消费)
Kafka学习---消费者(分区消费、分区平衡策略、offset、漏消费和重复消费)
2274 2
|
人工智能 测试技术 iOS开发
iOS性能指标和性能测试工具
iOS性能指标和性能测试工具
568 0
|
机器学习/深度学习 人工智能 算法
人工智能LLM模型:奖励模型的训练、PPO 强化学习的训练、RLHF
人工智能LLM模型:奖励模型的训练、PPO 强化学习的训练、RLHF
人工智能LLM模型:奖励模型的训练、PPO 强化学习的训练、RLHF
SpringBoot全局异常不生效分析与解决
SpringBoot全局异常不生效分析与解决
629 0