判断链表中是否有环（C语言）

给定一个链表，判断链表中是否有环。

题目链接：

示例1： 输出：true

示例2： 输出：true

示例3： 输出：false

解题思路：首先从环的性质入手，如果存在环，那么我若是使用一个指针遍历链表，这个指针将会一直在链表中的环里转圈圈。那要如何判断是否有环也就显而易见了：若是指针访问到了之前访问过的节点，那么链表有环，若是能遍历完链表，那肯定没有。 那么问题来了，怎么判断指针是否访问过了之前的节点？以下介绍三种方法：

方法1：暴力破解法，记录每个遍历过的节点地址，每访问一个节点就比较一次，若有相等的地址，则返回该地址值；

方法2：设置两个速度不同的指针同时从链表的第一个节点开始遍历链表，一个快指针 fp 每次移动两个节点，一个慢指针sp每次移动一个节点，若两个指针能相遇，则存在环。（注：这里的慢指针中保存的即为快指针访问过的节点）

方法3：将每个访问过的节点的 next 指针指向前一个节点，这样当指针访问到最后一个节点时，若该节点为头结点，则有环。但是这种方法破坏了链表的结构，不推荐使用。

下面讨论方法2的可行性。 对于方法2，可能有人会有疑问，为什么快指针 fp 一次只能移动两个节点，这样一定能判断出环吗？ 我先解释下为什么一次只能移动两个节点，如图所示： 假设环中有 n 个节点（n > 1），fp、sp 指向任意两个不同的节点，sp 每次移动 1 个节点，若 fp 每次移动 n + 1 个节点，那么一次操作后 因此，fp 每次不能移动 k 个节点，k满足 k % (n + 1) == 0，否则会出现死循环，那么为什么移动 2 个节点可以呢，很简单，因为 n 为1的时候两指针始终是相遇的。 以下是方法2的参考代码：

bool hasCycle(struct ListNode *head) {
          
   
    if(head == NULL){
          
   
        return false;
    }
    struct ListNode *pre = head->next;
    struct ListNode *lag = head;
    while(pre){
          
   
        if(lag == pre){
          
   
            return true;
        }
        lag = lag->next;
        pre = pre->next;            
        if(pre){
          
   
            pre = pre->next;
        }        
    }
    return false;
}

方法3的参考代码如下：

bool hasCycle(struct ListNode *head) {
          
   
    if(head == NULL || head->next == NULL){
          
   
        return false;
    }
    struct ListNode *before = head;
    struct ListNode *cur = head->next;
    struct ListNode *pre;
    before->next = NULL;
    while(cur){
          
   
        pre = cur->next;
        cur->next = before;
        before = cur;
        cur = pre;        
    }
    if(before == head){
          
   
        return true;
    }
    return false;
}

环形链表的进阶题：