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

一、问题描述

原题链接

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;
}