騰訊面試：龜兔賽跑判斷鏈表是否帶環(huán)

大家好，我是道哥。今天，我們來(lái)看一道非常有趣的騰訊面試題，題目如下：

有一個(gè)單鏈表，已知其頭指針，判斷它是否帶環(huán)？要求時(shí)空復(fù)雜度盡可能低。

帶環(huán)的單鏈表不太常見(jiàn)，比如：

如果你還處于懵圈的狀態(tài)，那也不要著急哦。比賽的賽道總應(yīng)該見(jiàn)過(guò)吧，且看直賽道和環(huán)賽道：

直賽道

接下來(lái)，我們來(lái)判斷賽道是否帶環(huán)，請(qǐng)注意要求：時(shí)間復(fù)雜度和空間復(fù)雜度盡可能低。

一. 暴力解法

不帶環(huán)，意味著一直往前走，必定會(huì)有盡頭，對(duì)吧！ 帶環(huán)，意味著一直往前走，總在循環(huán)中轉(zhuǎn)圈，沒(méi)有盡頭。

然而，這里的問(wèn)題是：“一直”是什么意思？到底走多久才算一直？這是我們遇到的難點(diǎn)，必須面對(duì)這個(gè)問(wèn)題。

總不能用while死循環(huán)來(lái)做吧，如果真有環(huán)，程序就陷入了死循環(huán)，無(wú)法走出來(lái)，那這個(gè)程序就沒(méi)啥意義了。

所以，必須考慮限制次數(shù)，比如往后走100萬(wàn)次，倘若還沒(méi)有終點(diǎn)，那么可以認(rèn)為這個(gè)鏈表就是帶環(huán)的鏈表。

稍微有點(diǎn)邏輯的人都知道，這個(gè)解法是不嚴(yán)密的，假如這個(gè)鏈表真的有200萬(wàn)個(gè)結(jié)點(diǎn)呢？那就明顯產(chǎn)生誤判。

我在LeetCode上驗(yàn)證了思路，發(fā)現(xiàn)居然通過(guò)了所有的測(cè)試用例，根本原因還是測(cè)試用例太少，Go代碼如下：

func hasCycle(head *ListNode) bool {
    count := 0    max := 1000000    for ; head != nil && count < max; {        count++        head = head.Next    }
    if count == max {        return true    }
    return false}

很顯然，這種不嚴(yán)密的暴力解法，無(wú)法通過(guò)騰訊的面試。

二. 標(biāo)記解法

接下來(lái)，我們思考下：環(huán)的本質(zhì)是什么？說(shuō)白了，環(huán)就是：總會(huì)走過(guò)曾經(jīng)走過(guò)的地方。是啊，好馬還吃回頭草呢？

正所謂走過(guò)路過(guò)不要錯(cuò)過(guò)，只要是走過(guò)的地方，都做一個(gè)標(biāo)記，下次如果再遇到，說(shuō)明這條路就是一條環(huán)狀的路。

具體很簡(jiǎn)單：把走過(guò)結(jié)點(diǎn)的地址，塞入到hashmap中，每走過(guò)一個(gè)結(jié)點(diǎn)，就判斷結(jié)點(diǎn)地址是否已在hashmap中。

可是，這里引入了哈希表，所以，空間復(fù)雜度就是O(N)了。顯然，這不是最好的方式，也自然沒(méi)法通過(guò)騰訊面試。

三. 龜兔賽跑

利用龜兔賽跑的啟發(fā)，我們可以有比較圓滿的解答，讓時(shí)間復(fù)雜度和空間復(fù)雜度盡可能低，并且能通過(guò)騰訊面試。

為了更形象直觀地呈現(xiàn)，我畫了兩張動(dòng)圖。對(duì)于直賽道而言，在龜兔賽跑中，烏龜是永遠(yuǎn)沒(méi)法追趕上兔子的。別忘了，兔子不會(huì)睡覺(jué)哦，如下：

對(duì)于環(huán)形賽道而言，兔子的速度遠(yuǎn)大于烏龜，所以，總有一天，兔子會(huì)再次追上烏龜。你看看兔子追上烏龜?shù)哪莻€(gè)得意的表情啊，高興壞了，Yeah:

?

受此啟發(fā)，我們可以在鏈表中考慮快慢指針，快指針每次走2步，慢指針每次走1步，這樣就完美地模擬了上述的龜兔賽跑場(chǎng)景。這次采用C++語(yǔ)言，程序如下：

#include<iostream>using namespace std; typedef struct node{    int data;      struct node *next;}Node; Node *createList(int n){    Node *p = new Node[n];    for( int i = 1; i < n; ++i)    {        p[i - 1].next = &p[i];        p[i - 1].data = i;    }    p[n - 1].next = NULL;    p[n - 1].data = n;    return p;} Node *createListWithRing(int n){    Node *p = new Node[n];    for( int i = 1; i < n; ++i)    {        p[i - 1].next = &p[i];        p[i - 1].data = i;    }    p[n - 1].next = &p[n/2];    p[n - 1].data = n;    return p;} //pFast相當(dāng)于兔子，pSlow相當(dāng)于烏龜bool listHasRing(Node *p){    Node *pSlow = &p[0];    Node *pFast = &p[1];    while(NULL != pSlow && NULL != pFast -> next)     {        if(pSlow == pFast)    {      return true;    }
        pSlow = pSlow -> next;        pFast = pFast -> next ->next;    }      return false;}
 int main(){    Node *head = createList(10);    cout << listHasRing(head) << endl;    delete [] head;      head = createListWithRing(10);    cout << listHasRing(head) << endl;    delete [] head;     return 0;}

經(jīng)測(cè)試，完全正確。龜兔賽跑，真的很有趣啊，也順便通過(guò)了騰訊的面試。

朋友，點(diǎn)個(gè)“贊”和“在看”鼓勵(lì)下唄