判断单链表中是否存在环

1.问题分析

（1）不带环的链表的最后一个结点的next指针是指向NULL，而带环链表没有类似的最后节点，所以无法判断带环链表的结束，也就无法通过遍历一遍链表来求取链表的长度。但是如果有一个指针在遍历时它最后会一直在环中重复打圈。因此我们可以使用快慢指针来判断(fast / slow)。如果链表带环那么当fast走到空指针时slow还未走到，他们不会相遇；当链表带环，那么当fast在环中一定会和slow相遇。
（2）慢指针slow向前一步，快指针fast应该向前几步呢？我们需要仔细分析。
情况一
假设慢指针走一步，快指针走两步：当slow刚要进环时，fast和slow之间相差N个结点。每一次slow走一步，fast走两步，fast都在追slow，并且每追一次两者之间距离都会缩小1，最后一定会变成0（两者相遇）。

情况二
假设慢指针走一步，快指针走三步：当N为偶数时，快慢指针会第一次就相遇。当N为奇数时，第一次快慢指针会恰好错过。这时候又分为两种情况。
1、当环的长度为偶数时：slow和fast之间的距离又变成奇数了，所以还会恰好错过，一直循环，无法相交
2.当环的长度为奇数时：slow和fast之间的距离变为偶数，则下次两者一定会相遇。

其余情况都会遇到与情况二相似的问题！！

2.代码实现

bool hasCycle(struct ListNode *head) {
    struct ListNode* slow = head, *fast = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
            return true;
    }
    return false;
}

若带环，求环的长度

1.问题分析

在上一个问题中，我们已经求得了快慢指针相遇的点，若让快慢指针自此从相遇点开始走，则再次相遇时，快指针比满指针多走的长度就是环的长度，同时，由于快指针每次比慢指针多走一步，所以多走的长度 = 慢指针走的长度 = 两个指针走的次数

2.代码实现

int CircleLong main()
{
    fast = slow = meet   //先将两个指针都定位在相遇点
    int count = 0;       //用于计数
    while(fast != slow)
    {
        fast = fast->next->next; 
        slow = slow->next;
        count++;
    }
    return count;
}

若带环，求环的连接点

问题分析

由定理：相遇点meet到环连接点的距离 = 头指针到连接点的距离。
所以我们让两个指针（正常指针，每次都走一步）分别从相遇点和头指针位置走，两个指针相遇的结点就是环的连接点。 证明如下：

2.代码实现

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow = head, *fast = head;  //初始化快慢指针
    while(fast && fast->next)       //当fast走到空，或者fast的下一个走到空，都是快指针遍历完链表
    {
        fast = fast->next->next;    //fast每次走两步
        slow = slow->next;          //fast每次走一步
        if(fast == slow)  //相遇
        {
            struct ListNode* meet = fast;
            while(meet != head)
            {
                meet = meet->next;      //从相遇点开始
                head = head->next;      //从头指针开始
            }
            return meet;           //返回连接点
        }
    }
    return NULL;  //没有相遇返回空指针
}