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

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

網站建設哪家好，找成都創(chuàng)新互聯(lián)！專注于網頁設計、網站建設、微信開發(fā)、重慶小程序開發(fā)、集團企業(yè)網站建設等服務項目。為回饋新老客戶創(chuàng)新互聯(liá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)的入口。

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

那么會有一個問題：

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

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

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

可以得出  s = nr

假設環(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)拋去轉的圈數(shù)，剛好就是相遇節(jié)點到環(huán)入口的距離 == 鏈頭節(jié)點到環(huán)入口的距離。

(L–a–x)為相遇點到環(huán)入口點的距離，由此可知，從鏈表頭到環(huán)入口點等于(n-1)循環(huán)內環(huán)+相遇點到環(huán)入口點，于是我們從鏈表頭、相遇點分別設一個指針，每次各走一步，兩個指針必定相遇，且相遇第一點為環(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é)點，我們可以先遍歷一個鏈表，直到尾部，再遍歷另外一個鏈表，如果也可以走到同樣的結尾點，則兩個鏈表相交。這時我們記下兩個鏈表length，再遍歷一次，長鏈表節(jié)點先出發(fā)前進(lengthMax-lengthMin)步，之后兩個鏈表同時前進，每次一步，相遇的第一點即為兩個鏈表相交的第一個點。

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

標題名稱：鏈表帶環(huán)問題求解？是否帶環(huán)，環(huán)的入口點，環(huán)長度-創(chuàng)新互聯(lián)
本文來源：http://jinyejixie.com/article4/diocie.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供網站維護、企業(yè)網站制作、做網站、動態(tài)網站、定制開發(fā)、網站導航

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)