鏈表帶環(huán)問題求解？是否帶環(huán)，環(huán)的入口點，環(huán)長度

(1)鏈表是否有環(huán)?

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

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)找到環(huán)的入口點？

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

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

那么會有一個問題：

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

當(dāng)慢指針和快指針相遇的時候，快指針必然在環(huán)中轉(zhuǎn)了n圈

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

可以得出  s = nr

假設(shè)環(huán)入口到相遇節(jié)點的距離為x，鏈頭節(jié)點到環(huán)入口的距離為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；我們發(fā)現(xiàn)拋去轉(zhuǎn)的圈數(shù)，剛好就是相遇節(jié)點到環(huán)入口的距離 == 鏈頭節(jié)點到環(huán)入口的距離。

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

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)如何知道環(huán)的長度？

記錄下碰撞點meet，slow、fast從該點開始，再次碰撞所走過的操作數(shù)就是環(huán)的長度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)帶環(huán)鏈表的長度是多少？

L=a+r。

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

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

比較好的方法有兩個：

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

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