💓 博客主页：倔强的石头的CSDN主页
📝Gitee主页：倔强的石头的gitee主页
⏩ 文章专栏：《数据结构与算法 经典例题》C语言
期待您的关注
目录
一、问题描述
二、解题思路
1.解题思路:
2.快慢指针的移动分三个阶段：（详细图解）
额外思考
三、代码实现
一、问题描述
原题链接
141. 环形链表 - 力扣（LeetCode）
二、解题思路
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;
}
