如何通過(guò)C++求出鏈表中環(huán)的入口結(jié)點(diǎn)

更新時(shí)間：2021年12月10日 10:34:18 作者：翟天保Steven

本文主要介紹了通過(guò)C++求解鏈表中環(huán)的入口結(jié)點(diǎn)，即給一個(gè)長(zhǎng)度為n鏈表，若其中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)，否則，返回null。需要的朋友可以參考一下

題目描述：

給一個(gè)長(zhǎng)度為n鏈表，若其中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)，否則，返回null。

數(shù)據(jù)范圍： n≤10000，1<=結(jié)點(diǎn)值<=10000

要求：空間復(fù)雜度 O(1)，時(shí)間復(fù)雜度 O(n)

例如，輸入{1,2},{3,4,5}時(shí)，對(duì)應(yīng)的環(huán)形鏈表如下圖所示：

可以看到環(huán)的入口結(jié)點(diǎn)的結(jié)點(diǎn)值為3，所以返回結(jié)點(diǎn)值為3的結(jié)點(diǎn)。

輸入描述：

輸入分為2段，第一段是入環(huán)前的鏈表部分，第二段是鏈表環(huán)的部分，后臺(tái)會(huì)根據(jù)第二段是否為空將這兩段組裝成一個(gè)無(wú)環(huán)或者有環(huán)單鏈表

返回值描述：

返回鏈表的環(huán)的入口結(jié)點(diǎn)即可，我們后臺(tái)程序會(huì)打印這個(gè)結(jié)點(diǎn)對(duì)應(yīng)的結(jié)點(diǎn)值；若沒(méi)有，則返回對(duì)應(yīng)編程語(yǔ)言的空結(jié)點(diǎn)即可。

示例：

輸入：

{1,2},{3,4,5}

返回值：

說(shuō)明：

返回環(huán)形鏈表入口結(jié)點(diǎn)，我們后臺(tái)程序會(huì)打印該環(huán)形鏈表入口結(jié)點(diǎn)對(duì)應(yīng)的結(jié)點(diǎn)值，即3

解題思路：

本題考察數(shù)據(jù)結(jié)構(gòu)鏈表的使用，有兩種解法。

哈希Set。用容器哈希Set遍歷存儲(chǔ)指針，當(dāng)某次存儲(chǔ)發(fā)現(xiàn)容器中已有該指針，說(shuō)明此時(shí)已經(jīng)到了環(huán)形鏈表入口。
快慢雙指針?lè)?。如下圖所示，快指針以慢指針兩倍的速度前進(jìn)，當(dāng)他們第一次相遇時(shí)，慢指針走了X+Y，快指針走了2*(X+Y)，其中AB為X，BC為Y，那CB順指針的距離就是2*(X+Y)-X-2*Y=X，此時(shí)將快指針?lè)诺筋^節(jié)點(diǎn)A處，讓它們以相同速度前進(jìn)，到B時(shí)正好相遇，也就是入口結(jié)點(diǎn)。

測(cè)試代碼：

解法一：哈希Set

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        unordered_set<ListNode*> S;
        while(pHead)
        {
            if(S.find(pHead)= = S.end())
            {
                S.insert(pHead);
                pHead = pHead->next;
            }
            else{
                return pHead;
            }
        }
        return nullptr;
    }
};

解法二：快慢雙指針?

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        // 空指針?lè)祷?
        if(pHead == nullptr) 
            return nullptr;
        
        // 定義雙指針
        ListNode* slow = pHead;
        ListNode* fast = pHead;
        
        // 當(dāng)能形成閉路時(shí)，while才會(huì)無(wú)限循環(huán)直到break
        while(fast != nullptr && fast->next != nullptr)
        {
            // 快指針以兩倍速度前進(jìn)
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast)
                break;
        }
        
        // 若指向空指針，說(shuō)明沒(méi)有形成閉路
        if(fast == nullptr || fast->next == nullptr)
            return nullptr;
        
        // 將快指針指向頭
        fast = pHead;
        
        // 當(dāng)他倆相遇時(shí)，就是環(huán)形鏈表入口處
        while(fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        
        return fast;
    }
};

到此這篇關(guān)于如何通過(guò)C++求出鏈表中環(huán)的入口結(jié)點(diǎn)的文章就介紹到這了,更多相關(guān)C++ 鏈表中環(huán)的入口結(jié)點(diǎn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: