一个链表的尾节点的next指针反而指向其他节点(包括自己)，就构成了一个带环链表。对带环链表问题的求解，往往涉及环的入口点和环的周长。本文着重介绍单向带环链表中求环的周长和环的入口的若干解法。

判断链表是否带环

假设一个链表有环，则该链表一定包含一段闭合回路，遍历链表的指针进入该回路后就会陷入不断循环。已知的是，在一个闭合回路中，若两个点的运动相对速度合适，则两个点一定会在回路中的某个位置相遇(重合)，所以可以利用追及运动证明环的存在。

为了分析方便，这里将带环链表进行抽象，整个链表包括非环部分和环。为了实现追及运动，分别定义快(fast)、慢(slow)指针遍历链表，fast指针一次走两步，slow指针一次走一步，可见当slow指针位于非环部分的中间时，fast开始进环；当slow指针开始进环时，fast指针已经绕环走了数圈，此时fast指针开始在环内追及slow指针。

在这种情形下，两指针一定会在环内的某一点(meet)相遇，下面给出逻辑证明。

证明一：

slow指针一次走一步，fast指针一次走两步，两指针一定会在环内相遇

假设slow开始进环时，fast与slow之间的距离为N，因为可能存在slow刚开始入环即与fast相遇的情况，固有

此时问题转化为了找相交链表的交点的问题，用双指针求解即可。这里附上求相交链表求交点的代码，不再进行详细的证明：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
    if(!headA || !headB)//其中一个为空，一定不相交 {
        return NULL;
    }
    struct ListNode* pA = headA;
    struct ListNode* pB = headB;

    while(pA != pB)//pA和pB都为空或在某节点相遇
    {
        pA = (pA == NULL ? headB : pA->next);
        pB = (pB == NULL ? headA : pB->next);
    }
    return pA;
}