朋友們、伙計(jì)們，我們又見(jiàn)面了，本期來(lái)給大家解讀一下LeetCode中第142道單鏈表OJ題，如果看完之后對(duì)你有一定的啟發(fā)，那么請(qǐng)留下你的三連，祝大家心想事成！

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-475688.html

數(shù)據(jù)結(jié)構(gòu)與算法專欄：數(shù)據(jù)結(jié)構(gòu)與算法

個(gè)? 人? 主? 頁(yè)?：stackY、

C 語(yǔ) 言 專 欄：C語(yǔ)言：從入門到精通

LeetCode--142.環(huán)形鏈表Ⅱ：?https://leetcode.cn/problems/linked-list-cycle-ii/description/

目錄

1.題目介紹

2.實(shí)例演示

3.解題思路

4.思路驗(yàn)證?

5.其他解題方法

1.題目介紹

給定一個(gè)鏈表的頭節(jié)點(diǎn) ?head?，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。?如果鏈表無(wú)環(huán)，則返回?null。

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過(guò)連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù) pos 來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒(méi)有環(huán)。注意：pos 不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。不允許修改 鏈表。

2.實(shí)例演示

3.解題思路

小編在這里給大家推薦比較簡(jiǎn)單的解題思路，同樣的都是使用快慢指針的，我們先來(lái)講具體的解題思路，后面會(huì)驗(yàn)證這種方法的正確性：

????????同樣的還是設(shè)置快慢指針，慢指針一次走一步，快指針一次走兩步，同樣的我們先來(lái)判斷鏈表是否有環(huán)（如何判斷鏈表有環(huán)大家可以去看LeetCode：141.環(huán)形鏈表這篇博客，里面包含了具體解題思路），在判斷是否有環(huán)之后呢，我們要找到第一次入環(huán)的節(jié)點(diǎn)，那這個(gè)就比較麻煩了，該怎么找呢？小編在這里給大家提供一個(gè)簡(jiǎn)單的解法：記錄環(huán)中快慢指針相遇的節(jié)點(diǎn)（meet），然后讓一個(gè)指針從鏈表的頭（head）開始走，一次都走一步，當(dāng)meet和head相遇時(shí)它們就是第一次入環(huán)的節(jié)點(diǎn)。

代碼演示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    //設(shè)置快慢指針
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    //快慢指針的相遇節(jié)點(diǎn)
    struct ListNode* meet = NULL;

    //判斷是否有環(huán)
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        //若有環(huán)則記錄快慢指針的相遇節(jié)點(diǎn)
        if(fast == slow)
        {
            meet = slow;
            //找第一次入環(huán)的節(jié)點(diǎn)
            while(meet != head)
            {
                //一次都走一步
                meet = meet->next;
                head = head->next;
            }

            return meet;
        }
    }
    //無(wú)環(huán)則返回NULL
    return NULL;
}

4.思路驗(yàn)證?

要求環(huán)形鏈表第一次入環(huán)的節(jié)點(diǎn)，我們使用的這種快慢指針的方法是很簡(jiǎn)單的，也是很巧妙的，這種方法具體是怎么實(shí)現(xiàn)的，讓我們接著往下來(lái)看：

我們假設(shè)環(huán)的長(zhǎng)度為C，鏈表的頭到第一次入環(huán)節(jié)點(diǎn)的距離為L(zhǎng)，第一次入環(huán)的節(jié)點(diǎn)到相遇點(diǎn)的距離為X。

慢指針在這里有一個(gè)分析問(wèn)題：slow有沒(méi)有可能在環(huán)里面轉(zhuǎn)了好幾圈快指針才追上？

答案是肯定不可能，因?yàn)榭熘羔樀乃俣仁锹羔樀?倍，不存在錯(cuò)過(guò)的情況，所以慢指針不存在走好幾圈才能被快指針追上的情況。

很多老鐵在這里驗(yàn)證的時(shí)候使用了一種錯(cuò)誤的驗(yàn)證方法：

慢指針slow走的路程是：L + X

快指針fast走的路程是：L + X + C

那么就有一種對(duì)應(yīng)的關(guān)系：2 * （L + X） =? L + X + C

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?L = C - X

這種方法有一個(gè)弊端，比如一個(gè)環(huán)形鏈表前面進(jìn)環(huán)的路程(L)非常的長(zhǎng)，而環(huán)(C)又非常的小，那這就出現(xiàn)問(wèn)題了：

所以呢我們可以將這種特殊的情況考慮進(jìn)去，那么我們應(yīng)該先算快指針fast走的路程：

快指針fast走的路程：L + n * C + X（n為慢指針進(jìn)環(huán)之前快指針在環(huán)里面走過(guò)的圈數(shù)）

慢指針slow走的路程是：L + X

那么就有一種對(duì)應(yīng)的關(guān)系：?2 * （L + X） =? L + X + n * C

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?L = n * C - X

那么這樣解釋起來(lái)就好多了，相遇節(jié)點(diǎn)到第一次入環(huán)的節(jié)點(diǎn)的距離為C - X

頭節(jié)點(diǎn)到第一次入環(huán)節(jié)點(diǎn)的距離為L(zhǎng)，那么根據(jù)?L = n * C - X這個(gè)對(duì)應(yīng)關(guān)系，就可以推出從相遇節(jié)點(diǎn)每次走一步，頭指針每一次走一步，當(dāng)它們兩個(gè)相遇的時(shí)候就是這個(gè)環(huán)形鏈表第一次入環(huán)的節(jié)點(diǎn)。

?

5.其他解題方法

除了上面我們驗(yàn)證的這個(gè)方法外，還有另外的一種方法，小編在這里只說(shuō)思路，感興趣的老鐵可以自己嘗試一下：

分割環(huán)形鏈表法：

可以記錄快慢指針的相遇節(jié)點(diǎn)，然后以這個(gè)相遇點(diǎn)為起點(diǎn)，保存并記錄相遇節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，然后將相遇節(jié)點(diǎn)和它的下一個(gè)節(jié)點(diǎn)斷開鏈接，將這個(gè)環(huán)一分為二，這時(shí)就轉(zhuǎn)換成了鏈表相交的問(wèn)題。

一個(gè)鏈表是從頭開始，另一個(gè)鏈表的頭是從相遇點(diǎn)的下一個(gè)節(jié)點(diǎn)，那么這兩個(gè)鏈表的相交節(jié)點(diǎn)就是第一次入環(huán)的節(jié)點(diǎn)。

感興趣的老鐵可以自己動(dòng)手寫一下完整的代碼。?

朋友們、伙計(jì)們，美好的時(shí)光總是短暫的，我們本期的的分享就到此結(jié)束，最后看完別忘了留下你們彌足珍貴的三連喔，感謝大家的支持！

?

?

到了這里，關(guān)于單鏈表OJ題：LeetCode--142.環(huán)形鏈表Ⅱ（判斷第一次入環(huán)的節(jié)點(diǎn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！