判断链表是否为环形链表
目录
一、题目
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
提示：
- 链表中节点的数目范围是
[0, 104] -105 <= Node.val <= 105pos为-1或者链表中的一个 有效索引 。
二、代码
bool hasCycle(struct ListNode *head) {
if(head == NULL || head->next == NULL)
return false;
struct ListNode *fast = head->next, *slow = head; //fast 和 slow要错开！
while(fast != slow && fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
if(fast && fast->next) //跳出循环：1.fast == null 或 fast->next == null 2.fast == slow
return true;
else
return false;
}快指针进入环之后，追赶slow指针，每次差距缩小1（一个走一步，一个走两步），所以一定可以追上！
三、疑点代码解析
1.初始化
由于while判断时，fast ！= slow才能进入循环。
所以fast与slow的初始化不能为同一位置！
struct ListNode *fast = head->next, *slow = head; //fast 和 slow要错开！
2.循环
while(fast != slow && fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
（1）循环的终止条件：1.指针为空 2. 指针指向的节点重合
（2）由于fast = fast->next->next; 所以fast不能为空，fast->next也不可以为空！
3.if判断
if(fast && fast->next) //跳出循环：1.fast == null 或 fast->next == null 2.fast == slow
return true;
else
return false;
标红的代码需要额外注意，不能只写if（fast）。
原因：跳出循环：1.fast == null 或 fast->next == null 2.fast == slow
只有当fast 与 fast->next都不为空时，才能保证fast == slow。
4.
if(head == NULL || head->next == NULL)
1）head == NULL要写在前面，否则
head->next == NULL在判断时，默认head已经不为空！
2）注意观察题目中节点的范围！
需要注意的是
在写if句的判断条件时，一定要根据跳出循环的所有情况去判断！
四、代码简化
bool hasCycle(struct ListNode *head) {
struct ListNode *fast = head, *slow = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
return true;
}
return false;
}原文地址：https://blog.csdn.net/2302_80190394/article/details/136989837
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！