【数据结构与算法】判断链表是否有环（图文详解）
举报
倔强的石头_
发表于 2025/09/05 22:26:59
2025/09/05
【摘要】 给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。这道题的解题思路主要涉及到“快慢指针”或“双指针”的方法。这种方法的关键在于，如果存在环，那么快指针最终会追上慢指针。
目录
一、问题描述
二、解题思路
1.解题思路:
2.快慢指针的移动分三个阶段：（详细图解）
额外思考
三、代码实现
一、问题描述
二、解题思路
1.解题思路:
从环形链表的特点入手——在环中的某个节点，通过next指针连续跟踪可以再次达到。
不过，想要通过比对指针是否循环回到了某个节点，是行不通的，因为无法得知链表是从哪个节点进入环的。
通过快慢指针可以实现判断——慢指针每次走一步，快指针每次走两步
假设存在环的话，快指针会先进环，此时慢指针在环外走了一半；
继续走，当慢指针进环时，快指针已经在环中走了一段时间；
此时快慢指针的相对位置未知，但也无须得知。
因为此时快慢指针都在环中，而快慢指针每移动一次，两者之间的距离都减小一步，当快慢指针相遇，就可以证明链表是带环的
如果快指针先走向了NULL，则说明链表不带环
这种方法的关键在于，如果存在环，那么快指针最终会追上慢指针。
2.快慢指针的移动分三个阶段：（详细图解）
（假设链表存在环的情况）
第一阶段: 从初始位置到快指针进环第二阶段: 从快指针进环 到 慢指针进环第三阶段: 从慢指针进环 到快指针追上慢指针
额外思考
如果链表带环，会出现快慢指针错过永远无法相遇的情况吗？
不会存在，因为在环中，快指针每次比慢指针多走一步，两个指针之前的距离每次近一步，在环内，快指针相对于慢指针的“速度差”是恒定的，即使环中只有一个节点，也会相遇
三、代码实现
思路的逻辑比较复杂不过，代码的实现相对简单
只需要定义两个快慢指针while循环遍历，快指针每次走两步，慢指针每次走一步
如果快慢指针指向节点相同，则说明链表带环如果快指针走到NULL，说明链表不带环
struct ListNode {
int val;
struct ListNode *next;
};
bool hasCycle(struct ListNode *head)
{
struct ListNode*slow,*fast;
slow=fast=head;
while(fast&&fast->next)
{
slow=slow->next;//注意应该先移动再判断
fast=fast->next->next;
if(slow==fast)//否则就会因为初始位置相同返回true
{
return true;
}
}
return false;
}
推荐
华为开发者空间发布
让每位开发者拥有一台云主机
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
数据结构
点赞
收藏
关注作者