我們在上節(jié)已經(jīng)討論過，如果一個單鏈表中由于某種原因(數(shù)據(jù)錯誤、內(nèi)存泄漏、測試人員瞎點等)存在了環(huán)路，那么所有基于next成員的遍歷都會輸出錯誤的結(jié)果或者出現(xiàn)死循環(huán)。避免這一問題的一個解決方案是通過插入次數(shù)來記錄單鏈表的長度，在遍歷時使用這個長度作為限制，來避免無限在環(huán)上跑圈兒，但是這種方法需要鏈表在整個生命周期內(nèi)被鏈表類封裝，但是，編碼實踐告訴我們，一般會出現(xiàn)環(huán)路異常的鏈表都是沒有經(jīng)過封裝的鏈表，那么對于沒有封裝的鏈表的第二個方案就是：判斷一個鏈表是否有環(huán)路并且找出這個環(huán)路。那么如何去檢驗一個鏈表存在環(huán)路呢？

我們的討論都是基于以如下節(jié)點形成的鏈表：

template<class elementType>
struct node {
    elementType data;
    node<elementType> *next;
    node(elementType _data = 0, node<elementType>* _next = nullptr) : data(_data), next(_next) {}
    bool operator==(const node<elementType> &x) {
        return this->data == x.data && this->next == x.next;
    }
};

首先，由簡單的邏輯思考可以知道：由于一個節(jié)點最多有一個指針，所以一個單鏈表最多只能存在1個圈，且有圈的鏈表沒有表明終止的NULL指針，否則一定會有一個元素存在著兩個next指針。這個圈是由于尾節(jié)點的next指針錯誤地指向了鏈表中的節(jié)點導(dǎo)致 (單鏈表的尾節(jié)點的next指針應(yīng)當(dāng)是nullptr，即空值)。

那么第一個判圈算法就很直觀了：

遍歷鏈表，記錄遍歷過的每一個鏈表節(jié)點的實例或者地址，當(dāng)發(fā)現(xiàn)某一個節(jié)點的next指針指向了已經(jīng)記錄過的節(jié)點時，就可以得出有圈的結(jié)論；反之，如果發(fā)現(xiàn)某一個節(jié)點的next指針是nullptr，則得出無圈結(jié)論。
記錄這個節(jié)點指針的方法可以使用數(shù)組或者散列。

那么實現(xiàn)一下：

樸素環(huán)路檢測

template<class elementType>
bool isCircleInChain(node<elementType>* head) {
    unordered_map<node<elementType>*, bool> history;
    while(head != nullptr) {
        if (history.find(head) != history.end()) //“如果在history中找到了指針head的訪問記錄”
            return true;
        history[head] = 1;  //插入head的訪問記錄
        head = head->next;
    }
    return false;
}

對于長度為n的鏈表，這種算法使用了O(n)的漸近額外空間復(fù)雜度和O(n)的漸近時間復(fù)雜度。它的優(yōu)勢在于可以直接找出是哪一個節(jié)點的next指針發(fā)生了偏轉(zhuǎn)導(dǎo)致圈的產(chǎn)生。（上述的程序不具備此功能，不僅是由于它的返回值不是指針類型，還由于它操作的指針是head而不是head->next）

Floyd環(huán)路檢測

考慮一個現(xiàn)實情境：一個快車和一個慢車同時同地出發(fā)，在一個環(huán)形道路上不停行駛，快車一定有某一個時刻從后方追上并且超過慢車。我們使用這個情景帶給我們的結(jié)論，將環(huán)形道路抽象為(可能帶環(huán)的)鏈表，將兩輛車抽象為兩個指針，兩個指針初始化為表頭的位置，我們讓快指針每次移動2(可以為任意大于1的數(shù)，但是為2時程序的編碼最為簡潔)個單元，慢指針每次移動1個單元，當(dāng)我們發(fā)現(xiàn)快指針與慢指針相等時(在初始化時的相等不計)，即表明鏈表中存在環(huán)路；當(dāng)我們訪問了null指針時，即表明鏈表存在盡頭，即沒有環(huán)。

有的同學(xué)可能會有這種考慮：“如果快指針在接近慢指針時剛好跳過了它，那么判斷不會失敗嗎？” 其實，如果快指針步數(shù)為2而慢指針步數(shù)為1，在上述“快指針在接近慢指針時剛好跳過了它”的情況發(fā)生之前的一個單位時間，快指針和慢指針必然是重合的；相似地，如果“快指針在接近慢指針時剛好在它的前一個”的情況發(fā)生之后的一個單位時間，快指針和慢指針將會重合。但是如果此處讓快指針步進(jìn)3，情況就會變得復(fù)雜。

也就是說，如果步長分別為2和1，那么只要慢指針進(jìn)入了環(huán)路，在最差情況下慢指針只需要繞行一整圈才可以得出結(jié)果，而最優(yōu)情況是慢指針進(jìn)入環(huán)就可以得出結(jié)果。所以對于一個總長為n的鏈表，這個算法的漸進(jìn)時間復(fù)雜度是O(n)，使用O(1)的額外空間。
所以編碼如下：

bool hasCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast) {
        fast = fast->next;
        if (fast) fast = fast->next; //避免訪問NULL指針的next成員
        slow = slow->next;
        if (fast && fast == slow) return true; //先判斷fast是否存在的目的是避免“輸入一個只有表頭節(jié)點的空表，輸出true”的情況
    }
    return false;
}

上述算法稱為Floyd環(huán)路檢測，對于長度為n的鏈表，這個算法使用了O(n)的漸進(jìn)時間復(fù)雜度和O(1)的空間復(fù)雜度，這種算法對于鏈表、有限狀態(tài)自動機(jī)等結(jié)構(gòu)的環(huán)路檢測效果很好。
如果我們希望求出圈的大小，我們可以在第一次相遇之后多跑一圈，記錄下次相遇所用的迭代次數(shù)，再加一點小學(xué)數(shù)學(xué)，就可以求出環(huán)路的長度。或者也可以使快指針停下來，僅僅通過慢指針即可求出環(huán)路的長度。

練習(xí)

1 編寫一個基于Floyd環(huán)路檢測的，可以返回環(huán)路長度的算法。
2 編寫一個基于Floyd環(huán)路檢測的，可以返回環(huán)路起點的算法