单链表判断环路及环路的入口

1. 遍历链表

将已经遍历过的节点放在一个hash表中，如果一个节点已经存在hash表中，说明有环。
时间复杂度:O(n)
空间复杂度:O(n)

2. 快慢指针

时间复杂度:O(n)
空间复杂度:O(1)
使用两个指针

判断环的存在：

设置两个指针fast和slow，初始值都指向头，slow每次前进1步，fast每次前进2步。
链表存在环：则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则是无环链表)。
链表不存在环：fast先行头到尾部为NULL，则是无环链表。

寻找环的入口点：

当fast按照每次2步，slow每次1步的方式走，发现fast和slow重合，确定了单向链表有环路。
接下来，让fast回到链表的头部，重新走，每次步长1，那么当fast和slow再次相遇的时候，就是环路的入口了。

证明：在fast和slow第一次相遇的时候，假定slow走了n步，环路的入口是在p步，那么
slow走的路径： p+c ＝ n； c为fast和slow相交点 距离环路入口的距离
fast走的路径： p+c+kL = 2n； L为环路的周长，k是整数
显然，如果从p+c点开始，slow再走n步的话，还可以回到p+c这个点。
同时，fast从头开始走，步长为1，经过n步，也会达到p+c这点。
显然，在这个过程中fast和slow只有前p步骤走的路径不同。所以当p1和p2再次重合的时候，必然是在链表的环路入口点上。

typedef int DataType;//节点中数据类型

typedef struct ListNode//节点数据结构
{
    DataType data;
    struct ListNode *next;
} ListNode;

ListNode *IsCycle(ListNode *plist)//判断是否带环
{
    ListNode *fast = plist;
    ListNode *slow = plist;

    while ((fast != NULL) && (fast->next != NULL))
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
            return fast;
    }
    return NULL;
}

//求环的长度
int GetCycleLen(ListNode *meetnode)
{
    ListNode *cur = NULL;
    int count = 1;

    cur = meetnode->next;
    while (cur != meetnode)
    {
        cur = cur->next;
        count++;
    }
    return count;
}

//求环的入口点
ListNode *GetCycleEnter(ListNode *plist, ListNode *meetnode)
{

    while (plist != meetnode)
    {
        plist = plist->next;
        meetnode = meetnode->next;
    }
    return plist;
}

参考文章
参考