鏈表帶環(huán)問(wèn)題求解？是否帶環(huán)，環(huán)的入口點(diǎn)，環(huán)長(zhǎng)度-創(chuàng)新互聯(lián)

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

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

網(wǎng)站建設(shè)哪家好，找成都創(chuàng)新互聯(lián)！專注于網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、重慶小程序開(kāi)發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了梅河口免費(fèi)建站歡迎大家使用！

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)的入口點(diǎn)？

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

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

那么會(huì)有一個(gè)問(wèn)題：

這倆個(gè)距離為什么會(huì)相等，我們來(lái)證明一下。

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

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

可以得出  s = nr

假設(shè)環(huán)入口到相遇節(jié)點(diǎn)的距離為x，鏈頭節(jié)點(diǎn)到環(huán)入口的距離為a，鏈表長(zhǎng)度為L(zhǎng)

所以有 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é)點(diǎn)到環(huán)入口的距離 == 鏈頭節(jié)點(diǎn)到環(huán)入口的距離。

(L–a–x)為相遇點(diǎn)到環(huán)入口點(diǎn)的距離，由此可知，從鏈表頭到環(huán)入口點(diǎn)等于(n-1)循環(huán)內(nèi)環(huán)+相遇點(diǎn)到環(huán)入口點(diǎn)，于是我們從鏈表頭、相遇點(diǎn)分別設(shè)一個(gè)指針，每次各走一步，兩個(gè)指針必定相遇，且相遇第一點(diǎn)為環(huán)入口點(diǎ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)的長(zhǎng)度？

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

L=a+r。

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

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

比較好的方法有兩個(gè)：

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

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

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

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

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

廣告

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