头歌实践教学平台数据结构与算法：02线性表——环形链表（拓展）

针对数据结构02线性表——环形链表（拓展）在头歌平台练习过程中的完成代码，每题思路单独在每一关中解释。如有其他需求请留言。

第一关

       本关任务：已知一个带头结点的单链表L，如果L中有环，返回true，如果L中没有环，返回false。 环：如果链表中有某个结点可以通过连续跟踪next指针再次到达，则链表中存在环。

        判断是否存在环可以使用快慢指针的方式，都是从头开始，慢指针一次走两步，快指针一次走两步，如果有环两个指针必然会在环中的某一点相遇，如果快指针已经走到尾了，那么就不存在环。

bool HasCycle(LinkList L) {
	/*---------------代码开始-----------------*/
    if(L -> next == NULL)     return false;
    LinkList a = L,b = L;
    while(b != NULL && b -> next != NULL)
    {
        a = a ->next;
        b = b -> next -> next;
        if(a == b)    return true;
    }
    return false;
    /*---------------代码结束-----------------*/
}

第二关

        已知一个带头结点的单链表L，如果L中有环，返回指向入环结点的序号，如果L中没有环，返回-1。 入环结点：链表开始入环的第一个结点。 结点序号：头结点序号为0，首元结点序号为1，依次类推。

        此关涉及一个推论：设置两个指针分别从头节点和快慢指针相遇的地方出发，每次移动一个节点，那么相遇处就是环的入口点，证明如下

        链表头到环入口长度为—s，

        环入口到相遇点长度为—x，

        相遇点到环入口长度为—y，

则相遇时，快指针路程：s + (x + y ) * k,其中x + y为环的长度，k为走过环的圈数，注意k大于1。慢指针路程：s + x;

因为快指针的路程是慢指针的路程的两倍，所以：（s + x）* 2 = s + (x + y) * k + x;

化简得：s = (x + y) * (k - 1) + y，可以得出：头节点到环入口处的距离等于相遇点到环入口的距离。

int DetectCycle(LinkList L) {
	/*---------------代码开始-----------------*/
    if(L -> next == NULL)     return -1;
    LinkList a = L,b = L;
    LinkList q = L,p;
    while(b != NULL && b -> next != NULL)
    {
        a = a -> next;
        b = b -> next -> next;
        if(a == b)
        {
            p = a;
            while(q ->next != p ->next)
            {
                q = q->next;
                p = p->next;
            }
            return q -> data;
        }
    }
    /*---------------代码结束-----------------*/
	return -1; //无环
}