【数据结构与算法 刷题系列】判断链表是否有环（图文详解）

一、问题描述 原题链接

141. 环形链表 - 力扣（LeetCode）

二、解题思路 1.解题思路:

从环形链表的特点入手——在环中的某个节点，通过next指针连续跟踪可以再次达到。不过，想要通过比对指针是否循环回到了某个节点，是行不通的，因为无法得知链表是从哪个节点进入环的。通过快慢指针可以实现判断——慢指针每次走一步，快指针每次走两步假设存在环的话，快指针会先进环，此时慢指针在环外走了一半；继续走，当慢指针进环时，快指针已经在环中走了一段时间；此时快慢指针的相对位置未知，但也无须得知。因为此时快慢指针都在环中，而快慢指针每移动一次，两者之间的距离都减小一步，当快慢指针相遇，就可以证明链表是带环的如果快指针先走向了NULL，则说明链表不带环

这种方法的关键在于，如果存在环，那么快指针最终会追上慢指针。

2.快慢指针的移动分三个阶段：（详细图解）（假设链表存在环的情况）

第一阶段: 从初始位置到快指针进环

第二阶段: 从快指针进环 到 慢指针进环

第三阶段: 从慢指针进环 到快指针追上慢指针

额外思考 如果链表带环，会出现快慢指针错过永远无法相遇的情况吗？

不会存在，因为在环中，快指针每次比慢指针多走一步，两个指针之前的距离每次近一步，在环内，快指针相对于慢指针的“速度差”是恒定的，即使环中只有一个节点，也会相遇

三、代码实现 思路的逻辑比较复杂

不过，代码的实现相对简单

只需要定义两个快慢指针

while循环遍历，快指针每次走两步，慢指针每次走一步

如果快慢指针指向节点相同，则说明链表带环

如果快指针走到NULL，说明链表不带环

代码语言：javascript复制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;

}