如何通過C++求出鏈表中環(huán)的入口結點

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

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

題目描述：

給一個長度為n鏈表，若其中包含環(huán)，請找出該鏈表的環(huán)的入口結點，否則，返回null。

數(shù)據范圍： n≤10000，1<=結點值<=10000

要求：空間復雜度 O(1)，時間復雜度 O(n)

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

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

輸入描述：

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

返回值描述：

返回鏈表的環(huán)的入口結點即可，我們后臺程序會打印這個結點對應的結點值；若沒有，則返回對應編程語言的空結點即可。

示例：

輸入：

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

返回值：

3

說明：

返回環(huán)形鏈表入口結點，我們后臺程序會打印該環(huán)形鏈表入口結點對應的結點值，即3

解題思路：

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

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

測試代碼：

解法一：哈希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) {
        // 空指針返回
        if(pHead == nullptr) 
            return nullptr;
        
        // 定義雙指針
        ListNode* slow = pHead;
        ListNode* fast = pHead;
        
        // 當能形成閉路時，while才會無限循環(huán)直到break
        while(fast != nullptr && fast->next != nullptr)
        {
            // 快指針以兩倍速度前進
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast)
                break;
        }
        
        // 若指向空指針，說明沒有形成閉路
        if(fast == nullptr || fast->next == nullptr)
            return nullptr;
        
        // 將快指針指向頭
        fast = pHead;
        
        // 當他倆相遇時，就是環(huán)形鏈表入口處
        while(fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        
        return fast;
    }
};

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

您可能感興趣的文章: