C语言判断链表中是否带环_c语言判断链表是否有环

LC链接：

环形链表

一，链表带环

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

例如：

如果我们通过指针cur访问，则该指针cur会一直在2，3，4三个节点之间打转

二，通过快慢指针判断链表是否带环

论述：

存在两个指向链表头节点的指针slow,fast，在slow指向下自身一个节点时fast指向自身下两个节点（slow每走一步，fast走两步），如果链表带环，slow,fast总会在某次指向同一个节点（相遇）

证明：

如果链表带环

1，当fast入环之后，slow还在指向环之前的某个节点

 

 2，当slow入环之后，fast指向环内某个节点

3，此时我们可以打个比方来理解slow,fast之间的关系，好比在环形跑道上A同学和B同学之间距离未知，但A同学的速度是B同学的两倍，在未来的某一时刻两者一定会相遇

回到链表，slow和fast之间存在多少个节点是未知的，但slow每走一个节点，fast就走两个节点，相对于slow就是fast走了一个节点。也就是说，slow和fast每移动一次两者之间的距离就减1，虽然两者之间的节点数是未知的，但一定是1的倍数，所以，经过一定次数的移动后，两者一定相遇

三，实现细节

注意对指针进行解引用操作时一定要判别被解引用的指针是否为空指针

ps：如果链表不带环，则fast迟早会指向NULL

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) 
{
    struct ListNode* slow=head;
    struct ListNode* fast=head;
 
    while(fast!=NULL)
    {
        slow=slow->next;
        fast=fast->next;
 
        if(fast==NULL)
        {
            return false;
        }
        else
        {
            fast=fast->next;
        }
 
        if(slow==fast)
        {
            return true;
        }
    }
 
    return false;   
}