如何判断单链表是否存在环

给定一个单链表，只给出头指针h：

1、如何判断是否存在环？

2、如何知道环的长度？

3、如何找出环的连接点在哪里？

4、带环链表的长度是多少？

解法：

1、对于问题1，使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。

2、对于问题2，记录下问题1的碰撞点p，slow、fast从该点开始，再次碰撞所走过的操作数就是环的长度s。

3、问题3：有定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。

该定理的证明如下：

当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：

2s = s + nr
s= nr

设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)

(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

4、问题3中已经求出连接点距离头指针的长度，加上问题2中求出的环的长度，二者之和就是带环单链表的长度

判断是否存在环的程序：

bool IsExitsLoop(slist *head)
{
    slist *slow = head, *fast = head;

    while ( fast && fast->next ) 
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }

    return !(fast == NULL || fast->next == NULL);
}

寻找环连接点（入口点）的程序：

slist* FindLoopPort(slist *head)
{
    slist *slow = head, *fast = head;

    while ( fast && fast->next ) 
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }

    if (fast == NULL || fast->next == NULL)
        return NULL;

    slow = head;
    while (slow != fast)
    {
         slow = slow->next;
         fast = fast->next;
    }

    return slow;
}

以下是我（theCambrian）自己在上述基础上写的两个函数，如有误，请小伙伴们批评指正：

ps：今天去某公司面试的时候问道这个题，自己回答的不是很全面，特此总结。

计算环的长度：

int LoopLength(slist *crossPoint)
{
    if ( crossPoint == NULL )
        return -1; //-1 表示无环！

    slist *slow = crossPoint;

    if ( slow->next == slow )
        return 1;

    if (slow->next->next == slow)
        return 2;

    slow = crossPoint->next;
    slist *fast = crossPoint->next->next;
    size_t loopLen = 1;
    while ( fast != slow )
    {
        fast = fast->next->next;
        slow = slow->next;
        ++loopLen;
    }
    return loopLen;
}

计算链表总长度：

int sumLinkLength(slist *crossPoint)
{
    if ( crossPoint == NULL )
        return -1;

    slist * pHead = head;
    slist * pCrossPoint = crossPoint;

    size_t cnt = 0;
    while ( pHead != pCrossPoint )
    {
        pCrossPoint = pCrossPoint->next;
        pHead = pHead->next;
        ++cnt;
    }
    return ( LoopLength(crossPoint) + cnt );
}

上半部分原文链接：http://blog.csdn.net/liuxialong/article/details/6555850