数据结构：判断链表是否有环，若有环找到环入口

categories:

• 数据结构

步骤一：判断链表是否有环，如果有，则返回相遇的节点，如果没有则返回NULL

算法：通过设置快慢指针来判断相遇，快指针一次走两个节点，慢指针一次走一个，若两个指针能相遇则说明有环，返回相遇的节点，若快指针走到NULL都没发生相遇，则说明没环，返回NULL

C语言代码：

LinkList Loop(LinkList plist)
{
    if (plist == NULL || plist->next == NULL)
    {
        return NULL;
    }

    LinkList p = plist; // 快指针
    LinkList q = plist; // 慢指针

    while (p != NULL && p->next != NULL) // p->next != NULL 保证快指针一次走两个节点能够成功
    {
        p = p->next->next;
        q = q->next;
        if (p == q)
        {
            return p;
        }
    }
    return NULL;
}

步骤二：找到有环链表的环的入口

算法一：通过数学推导来找入口，具体如下：
设置快慢指针，快指针一次走两个节点，慢指针一次走一个节点，如下图，plist为链表起点，m为环入口，s点为快慢指针相遇点。

当快慢指针相遇在s点，慢指针走过的路程为 x + y ,快指针走过的路程为x + y + (k +y) * n，n是快指针绕环的圈数。
因为快指针速度是慢指针二倍，快慢指针移动的时间相同，所以快指针的路程等于慢指针路程的二倍，即2(x + y) = x + y + (k + y)n
化解：x + y = (k + y)n
x + y = (k + y)(n - 1) + k+y
x = (k + y)(n-1) + k
该式里，右边(k + y)(n -1)是绕环的路程，即从plist起点开始到环入口的路程等于从相遇点s开始到m的路程加上绕环的路程
因而可以让两个速度相同的指针，一个从plist开始走，一个从s点开始走，二者第一次相遇的点就是环入口m点

C代码如下：

LinkList IsLoop(LinkList plist)
{
    LinkList s = Loop(plist);//通过上一步骤的Loop函数找到快慢指针相遇点
    if (s == NULL)
    {
        return NULL;
    }
    LinkList p = plist;
    LinkList q = s;

    while (p != q)
    {
        p = p->next;
        q = q->next;
    }
    return p;//p就是入环的第一个节点
}

算法二：遍历节点时把节点存储在一个表里，每次移动指针都在表里查看有无当前节点，若有出现重复则返回该节点，若无则继续遍历。该算法思路较为简单，但效率不高，O(n^2)
C代码：

#define TABLESIZE 10  
Linklist FindCircleStart(Linklist plist)//如果有环，找到入幻的第一个节点
{
    assert(plist != NULL);
    if (plist == NULL)        return NULL;
    Linklist p = plist;
    if (IsCircle(p))
    {
        //遍历p，把节点存起来，第一个出现重复的节点就是环的入口
        Linklist table[TABLESIZE];
        int i = 0;
        while (p)
        {
            table[i] = p;
            p = p->next;
            i++;
            if (i > TABLESIZE)
            {
                realloc(table, sizeof(table) * 2);
            }
            for (int j = 0; j < i; j++)//看已存的表里有没有重复的
            {
                for (int k = j +1; k < i; k++)
                {
                    if (table[k] == table[j])
                        return table[k];
                }
            }
        }
        return NULL;
    }
    else
        return NULL;

}