上篇文章介紹了數(shù)組，哈希表，字符串相關(guān)的算法，這篇文章介紹另一個(gè)重要的數(shù)據(jù)結(jié)構(gòu)，鏈表

鏈表特點(diǎn)

鏈表，和數(shù)組相比較的話，對(duì)于存儲(chǔ)空間更加靈活，不像是數(shù)組，必須要求連續(xù)的空間，而且在數(shù)組中刪除一個(gè)元素，就比較麻煩了，嚴(yán)格而言，刪除數(shù)組中的一個(gè)元素，需要將后面的所有元素都向前移動(dòng)。但是數(shù)組這種數(shù)據(jù)結(jié)構(gòu)也有特別優(yōu)秀的特點(diǎn)，就是查找的時(shí)間復(fù)雜度是O(1)。鏈表對(duì)存儲(chǔ)空間很靈活，不要求連續(xù)，刪除一個(gè)節(jié)點(diǎn)，只需要從整個(gè)鏈表中去掉就可以了。但是缺點(diǎn)就是查找的時(shí)間復(fù)雜度為O(n)。因此，究竟要用數(shù)組還是鏈表，要看項(xiàng)目的實(shí)際情況。

鏈表的節(jié)點(diǎn)可以理解為以下結(jié)構(gòu)

struct _Node;
typedef struct _Node {
struct _Node* next_;
} Node;

可以發(fā)現(xiàn)，鏈表結(jié)構(gòu)體中有一個(gè)指向下一個(gè)節(jié)點(diǎn)的next_，這也就是鏈表成鏈的關(guān)鍵。因此鏈表很容易考察對(duì)指針的理解，而指針，也就是處理鏈表相關(guān)問(wèn)題的關(guān)鍵。

典型算法題

典型的算法題如面試題23：鏈表中環(huán)的入口節(jié)點(diǎn)

題目：如果一個(gè)鏈表中包含環(huán)，如何找出環(huán)的入口節(jié)點(diǎn)？

這是一道典型的鏈表題。上面分析過(guò)，解決鏈表類問(wèn)題，最關(guān)鍵的就在于指針。對(duì)于這類問(wèn)題，我們往往用兩個(gè)指針，這兩個(gè)指針可以從相同的節(jié)點(diǎn)出發(fā)，也可以從不同的節(jié)點(diǎn)出發(fā)，可以兩指針的速度相同，也可以速度不同，巧妙的運(yùn)用這些技巧，就可以解決一些復(fù)雜的問(wèn)題。

比如解決這個(gè)問(wèn)題，就需要類似的技巧。首先要對(duì)問(wèn)題進(jìn)行分解。對(duì)于復(fù)雜的問(wèn)題，我們要想辦法將其分解為簡(jiǎn)單的問(wèn)題。比如這個(gè)問(wèn)題，就可以做如下分解：如何判斷鏈表中有環(huán)？如果有環(huán)的話，如何得到鏈表中環(huán)的個(gè)數(shù)？最后就是如何找到環(huán)的入口點(diǎn)？

判斷鏈表成環(huán)

首先解決第一個(gè)問(wèn)題，就是如何判斷鏈表中有環(huán)。什么情況下有環(huán)呢？就是其中某一個(gè)節(jié)點(diǎn)，他的下一個(gè)節(jié)點(diǎn)又指向了前面的節(jié)點(diǎn)，如此一來(lái)，這個(gè)鏈表，就永遠(yuǎn)找不到結(jié)尾了。就好像是一個(gè)跑道，一直在繞著圈跑，卻永遠(yuǎn)跑不到終點(diǎn)。有了這種啟發(fā)，我們是不是可以判斷鏈表的next有沒(méi)有終止呢？如果從頭開(kāi)始遍歷節(jié)點(diǎn)，如果某個(gè)節(jié)點(diǎn)的next_為nullptr，自然，就是沒(méi)有成環(huán)的鏈表。如果找不到next_為nullptr的節(jié)點(diǎn)，則就是成環(huán)的鏈表。這是一個(gè)基本的思路，但是如果判斷的條件是

while (node_->next_ != nullptr) {
node_ = node_->next_;
}
// 如果代碼走到這里說(shuō)明沒(méi)有成環(huán)

這種判斷有一個(gè)致命的錯(cuò)誤，就是在成環(huán)的鏈表中，while的判斷條件永遠(yuǎn)是true的，因此這個(gè)while循環(huán)是退出不了的。這當(dāng)然是不可容忍的。如何讓while循環(huán)可以停止呢？也就是如何在成環(huán)的條件下找到停止的條件呢？這就需要用到剛才提到過(guò)的雙指針?lè)椒?。其?shí)思想非常簡(jiǎn)單，比如兩個(gè)人賽跑，如果跑的快的那個(gè)人追上跑的慢的人，則跑道肯定成環(huán)。有了這種思想，我們定義兩個(gè)指針，這兩個(gè)指針都從鏈表的head開(kāi)始跑，一個(gè)指針每次跑一個(gè)節(jié)點(diǎn)，另一個(gè)指針每次跑兩個(gè)節(jié)點(diǎn)，這就是兩個(gè)指針從相同的位置，但是速度不同的典型用法。如果一次跑兩個(gè)節(jié)點(diǎn)的那個(gè)指針，碰到了node_->next_ == nullptr的情況，則說(shuō)明鏈表不成環(huán)。如果一次跑兩個(gè)節(jié)點(diǎn)的那個(gè)指針，追上了一次跑一個(gè)的那個(gè)指針，則說(shuō)明鏈表成環(huán)。

確定鏈表環(huán)個(gè)數(shù)

下面我們來(lái)解決第二個(gè)問(wèn)題，就是得到鏈表環(huán)中的個(gè)數(shù)。有了上一步的結(jié)果，如果成環(huán)的話，快指針會(huì)追上慢指針。追上的那個(gè)節(jié)點(diǎn)，肯定是環(huán)內(nèi)的某個(gè)節(jié)點(diǎn)。我們可以從這個(gè)節(jié)點(diǎn)開(kāi)始計(jì)數(shù)，讓指針從這個(gè)節(jié)點(diǎn)開(kāi)始出發(fā)，每次走一個(gè)節(jié)點(diǎn)，沒(méi)走一個(gè)節(jié)點(diǎn)，計(jì)數(shù)增加。由于這個(gè)指針是環(huán)內(nèi)的某個(gè)節(jié)點(diǎn)，因此，這個(gè)指針一定會(huì)回到他出發(fā)的地方。當(dāng)他再次回到起始的節(jié)點(diǎn)時(shí)，我們統(tǒng)計(jì)的計(jì)數(shù)，就是環(huán)內(nèi)節(jié)點(diǎn)的個(gè)數(shù)。

確定鏈表環(huán)起始節(jié)點(diǎn)

有了前面的結(jié)論，我們已經(jīng)知道鏈表是否成環(huán)，如果成環(huán)的話，環(huán)內(nèi)節(jié)點(diǎn)個(gè)數(shù)也清楚了?，F(xiàn)在讓我們找到環(huán)的起始節(jié)點(diǎn)。這里，我們還需要運(yùn)用雙指針的技巧，假設(shè)我們已經(jīng)知道了環(huán)內(nèi)的個(gè)數(shù)為k，我們可以定義兩個(gè)指針，其中一個(gè)指針從頭開(kāi)始出發(fā)，另一個(gè)指針從第k個(gè)節(jié)點(diǎn)開(kāi)始出發(fā)，兩個(gè)指針每次往前走一個(gè)節(jié)點(diǎn)，當(dāng)兩個(gè)節(jié)點(diǎn)相遇的時(shí)候，就是環(huán)內(nèi)的第一個(gè)節(jié)點(diǎn)。

小結(jié)

從上面的典型面試題可以看出，解決鏈表類問(wèn)題，靈活的使用指針是關(guān)鍵，特別的，我們經(jīng)常會(huì)使用雙指針的技巧，兩個(gè)指針可以從同一個(gè)節(jié)點(diǎn)出發(fā)，速度不同，也可以從不同的節(jié)點(diǎn)出發(fā)，速度相同等等。靈活的使用這些技巧，可以解決一些復(fù)雜的鏈表問(wèn)題。特別的，對(duì)于任何復(fù)雜的問(wèn)題，我們都要將其積極的拆分為簡(jiǎn)單的問(wèn)題。這樣才能化繁為簡(jiǎn)，一步一步的解決問(wèn)題。