鏈表帶環問題求解？是否帶環，環的入口點，環長度

(1)鏈表是否有環?

設置兩個指針(fast, slow)，初始值都指向頭，slow每次前進一步，fast每次前進二步，如果鏈表存在環，則fast必定先進入環，而slow后進入環，兩個指針必定相遇，設碰撞點為p。(當然，fast如果為NULL，則為無環鏈表)程序如下：

bool IsExitsLoop(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 false;

    return true;
}

(2)找到環的入口點？

定理：slow和fast相遇點為p，讓slow從head開始，fast從p開始，每次往后各走一步，直到slow和fast再次相遇，則相遇點即為環的入口。

當快慢指針第一次相遇的時候，從相遇那個節點到環入口的節點和鏈表頭結點到環入口的節點的距離相等，所以此時讓一個指針從鏈頭開始跑，一個指針從相遇的節點開始跑，那么相遇時，這個相遇節點便是環的入口節點。

那么會有一個問題：

這倆個距離為什么會相等，我們來證明一下。

當慢指針和快指針相遇的時候，快指針必然在環中轉了n圈

所以有：2s = s + nr ；  s為慢指針走過的距離，r 為環的長度

可以得出  s = nr

假設環入口到相遇節點的距離為x，鏈頭節點到環入口的距離為a，鏈表長度為L

所以有 x + a = s  ；由上面替換得到  x + a = nr   ==> x+ a =(n-1)r +r ==> x + a = (n-1)r +L - a 

所以有  a = (n-1)r +L - a - x；我們發現拋去轉的圈數，剛好就是相遇節點到環入口的距離 == 鏈頭節點到環入口的距離。

(L–a–x)為相遇點到環入口點的距離，由此可知，從鏈表頭到環入口點等于(n-1)循環內環+相遇點到環入口點，于是我們從鏈表頭、相遇點分別設一個指針，每次各走一步，兩個指針必定相遇，且相遇第一點為環入口點。

ListNode *FindLoopPort(slist *head)
{
    ListNode *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;
}

(3)如何知道環的長度？

記錄下碰撞點meet，slow、fast從該點開始，再次碰撞所走過的操作數就是環的長度r。

unsigned int GetLoopLength(slist *head)
{
    ListNode*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 0;

    ListNode *meet = slow;
    slow = meet->next;
    fast = meet->next->next;
    unsigned int len = 1;
    while (slow != fast)
    {
        len ++;
        slow = slow->next;
        fast = fast->next->next;
    }

    return len;
}

(4)帶環鏈表的長度是多少？

L=a+r。

(5)判斷兩個單鏈表是否相交？

判斷兩個單鏈表是否相交，如果相交，給出相交的第一個點（兩個鏈表都不存在環）。

比較好的方法有兩個：

一、將其中一個鏈表L2首尾相連，檢測另外一個鏈表L1是否存在環，如果存在，則兩個鏈表相交，而檢測出來的依賴環入口即為相交的第一個點。

二、如果兩個鏈表相交，那個兩個鏈表從相交點到鏈表結束都是相同的節點，我們可以先遍歷一個鏈表，直到尾部，再遍歷另外一個鏈表，如果也可以走到同樣的結尾點，則兩個鏈表相交。這時我們記下兩個鏈表length，再遍歷一次，長鏈表節點先出發前進(lengthMax-lengthMin)步，之后兩個鏈表同時前進，每次一步，相遇的第一點即為兩個鏈表相交的第一個點。