鏈表（下）：如何輕松寫出正確的鏈表代碼？
上一節(jié)我講了鏈表相關(guān)的基礎(chǔ)知識(shí)。學(xué)完之后，我看到有人留言說，基礎(chǔ)知識(shí)我都掌握了，但是寫鏈表代碼還是很費(fèi)勁。哈哈，的確是這樣的！
想要寫好鏈表代碼并不是容易的事兒，尤其是那些復(fù)雜的鏈表操作，比如鏈表反轉(zhuǎn)、有序鏈表合并等，寫的時(shí)候非常容易出錯(cuò)。從我上百場(chǎng)面試的經(jīng)驗(yàn)來看，能把“鏈表反轉(zhuǎn)”這幾行代碼寫對(duì)的人不足 10%。
為什么鏈表代碼這么難寫？究竟怎樣才能比較輕松地寫出正確的鏈表代碼呢？
只要愿意投入時(shí)間，我覺得大多數(shù)人都是可以學(xué)會(huì)的。比如說，如果你真的能花上一個(gè)周末或者一整天的時(shí)間，就去寫鏈表反轉(zhuǎn)這一個(gè)代碼，多寫幾遍，一直練到能毫不費(fèi)力地寫出 Bug free 的代碼。這個(gè)坎還會(huì)很難跨嗎？
當(dāng)然，自己有決心并且付出精力是成功的先決條件，除此之外，我們還需要一些方法和技巧。我根據(jù)自己的學(xué)習(xí)經(jīng)歷和工作經(jīng)驗(yàn)，總結(jié)了幾個(gè)寫鏈表代碼技巧。如果你能熟練掌握這幾個(gè)技巧，加上你的主動(dòng)和堅(jiān)持，輕松拿下鏈表代碼完全沒有問題。
技巧一：理解指針或引用的含義
事實(shí)上，看懂鏈表的結(jié)構(gòu)并不是很難，但是一旦把它和指針混在一起，就很容易讓人摸不著頭腦。所以，要想寫對(duì)鏈表代碼，首先就要理解好指針。
我們知道，有些語言有“指針”的概念，比如 C 語言；有些語言沒有指針，取而代之的是“引用”，比如 Java、Python。不管是“指針”還是“引用”，實(shí)際上，它們的意思都是一樣的，都是存儲(chǔ)所指對(duì)象的內(nèi)存地址。
接下來，我會(huì)拿 C 語言中的“指針”來講解，如果你用的是 Java 或者其他沒有指針的語言也沒關(guān)系，你把它理解成“引用”就可以了。
實(shí)際上，對(duì)于指針的理解，你只需要記住下面這句話就可以了：
將某個(gè)變量賦值給指針，實(shí)際上就是將這個(gè)變量的地址賦值給指針，或者反過來說，指針中存儲(chǔ)了這個(gè)變量的內(nèi)存地址，指向了這個(gè)變量，通過指針就能找到這個(gè)變量。
這句話聽起來還挺拗口的，你可以先記住。我們回到鏈表代碼的編寫過程中，我來慢慢給你解釋。
在編寫鏈表代碼的時(shí)候，我們經(jīng)常會(huì)有這樣的代碼：p->next=q。這行代碼是說，p 結(jié)點(diǎn)中的 next 指針存儲(chǔ)了 q 結(jié)點(diǎn)的內(nèi)存地址。
還有一個(gè)更復(fù)雜的，也是我們寫鏈表代碼經(jīng)常會(huì)用到的：p->next=p->next->next。這行代碼表示，p 結(jié)點(diǎn)的 next 指針存儲(chǔ)了 p 結(jié)點(diǎn)的下下一個(gè)結(jié)點(diǎn)的內(nèi)存地址。
掌握了指針或引用的概念，你應(yīng)該可以很輕松地看懂鏈表代碼。恭喜你，已經(jīng)離寫出鏈表代碼近了一步！
技巧二：警惕指針丟失和內(nèi)存泄漏
不知道你有沒有這樣的感覺，寫鏈表代碼的時(shí)候，指針指來指去，一會(huì)兒就不知道指到哪里了。所以，我們?cè)趯懙臅r(shí)候，一定注意不要弄丟了指針。
指針往往都是怎么弄丟的呢？我拿單鏈表的插入操作為例來給你分析一下。
如圖所示，我們希望在結(jié)點(diǎn) a 和相鄰的結(jié)點(diǎn) b 之間插入結(jié)點(diǎn) x，假設(shè)當(dāng)前指針 p 指向結(jié)點(diǎn) a。如果我們將代碼實(shí)現(xiàn)變成下面這個(gè)樣子，就會(huì)發(fā)生指針丟失和內(nèi)存泄露。
p->next = x; //將p的next指針指向x結(jié)點(diǎn)
x->next = p->next; //將x的結(jié)點(diǎn)的next指針指向b結(jié)點(diǎn)
初學(xué)者經(jīng)常會(huì)在這兒犯錯(cuò)。p->next 指針在完成第一步操作之后，已經(jīng)不再指向結(jié)點(diǎn) b 了，而是指向結(jié)點(diǎn) x。第 2 行代碼相當(dāng)于將 x 賦值給 x->next，自己指向自己。因此，整個(gè)鏈表也就斷成了兩半，從結(jié)點(diǎn) b 往后的所有結(jié)點(diǎn)都無法訪問到了。
對(duì)于有些語言來說，比如 C 語言，內(nèi)存管理是由程序員負(fù)責(zé)的，如果沒有手動(dòng)釋放結(jié)點(diǎn)對(duì)應(yīng)的內(nèi)存空間，就會(huì)產(chǎn)生內(nèi)存泄露。所以，我們插入結(jié)點(diǎn)時(shí)，一定要注意操作的順序，要先將結(jié)點(diǎn) x 的 next 指針指向結(jié)點(diǎn) b，再把結(jié)點(diǎn) a 的 next 指針指向結(jié)點(diǎn) x，這樣才不會(huì)丟失指針，導(dǎo)致內(nèi)存泄漏。所以，對(duì)于剛剛的插入代碼，我們只需要把第 1 行和第 2 行代碼的順序顛倒一下就可以了。
同理，刪除鏈表結(jié)點(diǎn)時(shí)，也一定要記得手動(dòng)釋放內(nèi)存空間，否則，也會(huì)出現(xiàn)內(nèi)存泄漏的問題。當(dāng)然，對(duì)于像 Java 這種虛擬機(jī)自動(dòng)管理內(nèi)存的編程語言來說，就不需要考慮這么多了。
技巧三：利用哨兵簡(jiǎn)化實(shí)現(xiàn)難度
首先，我們先來回顧一下單鏈表的插入和刪除操作。如果我們?cè)诮Y(jié)點(diǎn) p 后面插入一個(gè)新的結(jié)點(diǎn)，只需要下面兩行代碼就可以搞定。
new_node->next = p->next;
p->next = new_node;
但是，當(dāng)我們要向一個(gè)空鏈表中插入第一個(gè)結(jié)點(diǎn)，剛剛的邏輯就不能用了。我們需要進(jìn)行下面這樣的特殊處理，其中 head 表示鏈表的頭結(jié)點(diǎn)。所以，從這段代碼，我們可以發(fā)現(xiàn)，對(duì)于單鏈表的插入操作，第一個(gè)結(jié)點(diǎn)和其他結(jié)點(diǎn)的插入邏輯是不一樣的。
if( head == NULL){
head = new_node;
}
我們?cè)賮砜磫捂湵斫Y(jié)點(diǎn)刪除操作。如果要?jiǎng)h除結(jié)點(diǎn)P的后繼結(jié)點(diǎn)，前面的刪除代碼就不行了。跟插入類似，我們也需要對(duì)這樣情況特殊處理。寫成代碼是這樣的：
if (head->next == NULL){
head = null;
}
從前面的一步一步分析，我們可以看出，針對(duì)鏈表的插入、刪除操作，需要對(duì)插入第一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)的情況進(jìn)行特殊處理。這樣代碼實(shí)現(xiàn)起來就會(huì)很繁瑣，不簡(jiǎn)潔，而且也容易因?yàn)榭紤]不全而出錯(cuò)。如何來解決這個(gè)問題呢？
技巧三中提到的哨兵就要登場(chǎng)了。哨兵，解決的是國(guó)家之間的邊界問題。同理，這里說的哨兵也是解決“邊界問題”的，不直接參與業(yè)務(wù)邏輯。
還記得如何表示一個(gè)空鏈表嗎？head=null 表示鏈表中沒有結(jié)點(diǎn)了。其中 head 表示頭結(jié)點(diǎn)指針，指向鏈表中的第一個(gè)結(jié)點(diǎn)。
如果我們引入哨兵結(jié)點(diǎn)，在任何時(shí)候，不管鏈表是不是空，head 指針都會(huì)一直指向這個(gè)哨兵結(jié)點(diǎn)。我們也把這種有哨兵結(jié)點(diǎn)的鏈表叫帶頭鏈表。相反，沒有哨兵結(jié)點(diǎn)的鏈表就叫作不帶頭鏈表。
我畫了一個(gè)帶頭鏈表，你可以發(fā)現(xiàn)，哨兵結(jié)點(diǎn)是不存儲(chǔ)數(shù)據(jù)的。因?yàn)樯诒Y(jié)點(diǎn)一直存在，所以插入第一個(gè)結(jié)點(diǎn)和插入其他結(jié)點(diǎn)，刪除最后一個(gè)結(jié)點(diǎn)和刪除其他結(jié)點(diǎn)，都可以統(tǒng)一為相同的代碼實(shí)現(xiàn)邏輯了。
實(shí)際上，這種利用哨兵簡(jiǎn)化編程難度的技巧，在很多代碼實(shí)現(xiàn)中都有用到，比如插入排序、歸并排序、動(dòng)態(tài)規(guī)劃等。這些內(nèi)容我們后面才會(huì)講，現(xiàn)在為了讓你感受更深，我再舉一個(gè)非常簡(jiǎn)單的例子。代碼我是用 C 語言實(shí)現(xiàn)的，不涉及語言方面的高級(jí)語法，很容易看懂，你可以類比到你熟悉的語言。
代碼一：
// 在數(shù)組 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示數(shù)組 a 的長(zhǎng)度
int find(char* a, int n, char key) {
// 邊界條件處理，如果 a 為空，或者 n<=0，說明數(shù)組中沒有數(shù)據(jù)，就不用 while 循環(huán)比較了
if(a == null || n <= 0) {
return -1;
}
int i = 0;
// 這里有兩個(gè)比較操作：i<n 和 a[i]==key.
while (i < n) {
if (a[i] == key) {
return i;
}
++i;
}
return -1;
}
代碼二：
// 在數(shù)組 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示數(shù)組 a 的長(zhǎng)度
// 我舉 2 個(gè)例子，你可以拿例子走一下代碼
// a = {4, 2, 3, 5, 9, 6} n=6 key = 7
// a = {4, 2, 3, 5, 9, 6} n=6 key = 6
inf find(char* a, int n, char key) {
if(a == null || n <= 0) {
return -1;
}
// 這里因?yàn)橐獙?a[n-1] 的值替換成 key，所以要特殊處理這個(gè)值
if (a[n-1] == key) {
return n-1;
}
// 把 a[n-1] 的值臨時(shí)保存在變量 tmp 中，以便之后恢復(fù)。tmp=6。
// 之所以這樣做的目的是：希望 find() 代碼不要改變 a 數(shù)組中的內(nèi)容
char tmp = a[n-1];
// 把 key 的值放到 a[n-1] 中，此時(shí) a = {4, 2, 3, 5, 9, 7}
a[n-1] = key;
int i = 0;
// while 循環(huán)比起代碼一，少了 i<n 這個(gè)比較操作
while (a[i] != key) {
++i;
}
// 恢復(fù) a[n-1] 原來的值, 此時(shí) a= {4, 2, 3, 5, 9, 6}
a[n-1] = tmp;
if (i == n-1) {
// 如果 i == n-1 說明，在 0...n-2 之間都沒有 key，所以返回 -1
return -1;
} else {
// 否則，返回 i，就是等于 key 值的元素的下標(biāo)
return i;
}
}
對(duì)比兩段代碼，在字符串 a 很長(zhǎng)的時(shí)候，比如幾萬、幾十萬，你覺得哪段代碼運(yùn)行得更快點(diǎn)呢？答案是代碼二，因?yàn)閮啥未a中執(zhí)行次數(shù)最多就是 while 循環(huán)那一部分。第二段代碼中，我們通過一個(gè)哨兵 a[n-1] = key，成功省掉了一個(gè)比較語句 i<n，不要小看這一條語句，當(dāng)累積執(zhí)行萬次、幾十萬次時(shí)，累積的時(shí)間就很明顯了。
當(dāng)然，這只是為了舉例說明哨兵的作用，你寫代碼的時(shí)候千萬不要寫第二段那樣的代碼，因?yàn)榭勺x性太差了。大部分情況下，我們并不需要如此追求極致的性能。
技巧四：重點(diǎn)留意邊界條件處理
軟件開發(fā)中，代碼在一些邊界或者異常情況下，最容易產(chǎn)生 Bug。鏈表代碼也不例外。要實(shí)現(xiàn)沒有 Bug 的鏈表代碼，一定要在編寫的過程中以及編寫完成之后，檢查邊界條件是否考慮全面，以及代碼在邊界條件下是否能正確運(yùn)行。
我經(jīng)常用來檢查鏈表代碼是否正確的邊界條件有這樣幾個(gè)：
如果鏈表為空時(shí)，代碼是否能正常工作？
如果鏈表只包含一個(gè)結(jié)點(diǎn)時(shí)，代碼是否能正常工作？
如果鏈表只包含兩個(gè)結(jié)點(diǎn)時(shí)，代碼是否能正常工作？
代碼邏輯在處理頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的時(shí)候，是否能正常工作？
當(dāng)你寫完鏈表代碼之后，除了看下你寫的代碼在正常的情況下能否工作，還要看下在上面我列舉的幾個(gè)邊界條件下，代碼仍然能否正確工作。如果這些邊界條件下都沒有問題，那基本上可以認(rèn)為沒有問題了。
當(dāng)然，邊界條件不止我列舉的那些。針對(duì)不同的場(chǎng)景，可能還有特定的邊界條件，這個(gè)需要你自己去思考，不過套路都是一樣的。
實(shí)際上，不光光是寫鏈表代碼，你在寫任何代碼時(shí)，也千萬不要只是實(shí)現(xiàn)業(yè)務(wù)正常情況下的功能就好了，一定要多想想，你的代碼在運(yùn)行的時(shí)候，可能會(huì)遇到哪些邊界情況或者異常情況。遇到了應(yīng)該如何應(yīng)對(duì)，這樣寫出來的代碼才夠健壯！
技巧五：舉例畫圖，輔助思考
對(duì)于稍微復(fù)雜的鏈表操作，比如前面我們提到的單鏈表反轉(zhuǎn)，指針一會(huì)兒指這，一會(huì)兒指那，一會(huì)兒就被繞暈了?？偢杏X腦容量不夠，想不清楚。所以這個(gè)時(shí)候就要使用大招了，舉例法和畫圖法。
你可以找一個(gè)具體的例子，把它畫在紙上，釋放一些腦容量，留更多的給邏輯思考，這樣就會(huì)感覺到思路清晰很多。比如往單鏈表中插入一個(gè)數(shù)據(jù)這樣一個(gè)操作，我一般都是把各種情況都舉一個(gè)例子，畫出插入前和插入后的鏈表變化，如圖所示：
看圖寫代碼，是不是就簡(jiǎn)單多啦？而且，當(dāng)我們寫完代碼之后，也可以舉幾個(gè)例子，畫在紙上，照著代碼走一遍，很容易就能發(fā)現(xiàn)代碼中的 Bug。
技巧六：多寫多練，沒有捷徑
如果你已經(jīng)理解并掌握了我前面所講的方法，但是手寫鏈表代碼還是會(huì)出現(xiàn)各種各樣的錯(cuò)誤，也不要著急。因?yàn)槲易铋_始學(xué)的時(shí)候，這種狀況也持續(xù)了一段時(shí)間。
現(xiàn)在我寫這些代碼，簡(jiǎn)直就和“玩兒”一樣，其實(shí)也沒有什么技巧，就是把常見的鏈表操作都自己多寫幾遍，出問題就一點(diǎn)一點(diǎn)調(diào)試，熟能生巧！
所以，我精選了 5 個(gè)常見的鏈表操作。你只要把這幾個(gè)操作都能寫熟練，不熟就多寫幾遍，我保證你之后再也不會(huì)害怕寫鏈表代碼。
單鏈表反轉(zhuǎn)
鏈表中環(huán)的檢測(cè)
兩個(gè)有序的鏈表合并
刪除鏈表倒數(shù)第 n 個(gè)結(jié)點(diǎn)
求鏈表的中間結(jié)點(diǎn)
內(nèi)容小結(jié)
這節(jié)我主要和你講了寫出正確鏈表代碼的六個(gè)技巧。分別是理解指針或引用的含義、警惕指針丟失和內(nèi)存泄漏、利用哨兵簡(jiǎn)化實(shí)現(xiàn)難度、重點(diǎn)留意邊界條件處理，以及舉例畫圖、輔助思考，還有多寫多練。
我覺得，寫鏈表代碼是最考驗(yàn)邏輯思維能力的。因?yàn)椋湵泶a到處都是指針的操作、邊界條件的處理，稍有不慎就容易產(chǎn)生 Bug。鏈表代碼寫得好壞，可以看出一個(gè)人寫代碼是否夠細(xì)心，考慮問題是否全面，思維是否縝密。所以，這也是很多面試官喜歡讓人手寫鏈表代碼的原因。所以，這一節(jié)講到的東西，你一定要自己寫代碼實(shí)現(xiàn)一下，才有效果。
課后思考
今天我們講到用哨兵來簡(jiǎn)化編碼實(shí)現(xiàn)，你是否還能夠想到其他場(chǎng)景，利用哨兵可以大大地簡(jiǎn)化編碼難度？
精彩評(píng)論
總結(jié)：如何優(yōu)雅的寫出鏈表代碼？6大學(xué)習(xí)技巧
一、理解指針或引用的含義
1.含義：將某個(gè)變量（對(duì)象）賦值給指針（引用），實(shí)際上就是就是將這個(gè)變量（對(duì)象）的地址賦值給指針（引用）。
2.示例：
p—>next = q; 表示p節(jié)點(diǎn)的后繼指針存儲(chǔ)了q節(jié)點(diǎn)的內(nèi)存地址。
p—>next = p—>next—>next; 表示p節(jié)點(diǎn)的后繼指針存儲(chǔ)了p節(jié)點(diǎn)的下下個(gè)節(jié)點(diǎn)的內(nèi)存地址。
二、警惕指針丟失和內(nèi)存泄漏（單鏈表）
1.插入節(jié)點(diǎn)
在節(jié)點(diǎn)a和節(jié)點(diǎn)b之間插入節(jié)點(diǎn)x，b是a的下一節(jié)點(diǎn)，，p指針指向節(jié)點(diǎn)a，則造成指針丟失和內(nèi)存泄漏的代碼：p—>next = x;x—>next = p—>next; 顯然這會(huì)導(dǎo)致x節(jié)點(diǎn)的后繼指針指向自身。
正確的寫法是2句代碼交換順序，即：x—>next = p—>next; p—>next = x;
2.刪除節(jié)點(diǎn)
在節(jié)點(diǎn)a和節(jié)點(diǎn)b之間刪除節(jié)點(diǎn)b，b是a的下一節(jié)點(diǎn)，p指針指向節(jié)點(diǎn)a：p—>next = p—>next—>next;
三、利用“哨兵”簡(jiǎn)化實(shí)現(xiàn)難度
1.什么是“哨兵”？
鏈表中的“哨兵”節(jié)點(diǎn)是解決邊界問題的，不參與業(yè)務(wù)邏輯。如果我們引入“哨兵”節(jié)點(diǎn)，則不管鏈表是否為空，head指針都會(huì)指向這個(gè)“哨兵”節(jié)點(diǎn)。我們把這種有“哨兵”節(jié)點(diǎn)的鏈表稱為帶頭鏈表，相反，沒有“哨兵”節(jié)點(diǎn)的鏈表就稱為不帶頭鏈表。
2.未引入“哨兵”的情況
如果在p節(jié)點(diǎn)后插入一個(gè)節(jié)點(diǎn)，只需2行代碼即可搞定：
new_node—>next = p—>next;
p—>next = new_node;
但，若向空鏈表中插入一個(gè)節(jié)點(diǎn)，則代碼如下：
if(head == null){
head = new_node;
}
如果要?jiǎng)h除節(jié)點(diǎn)p的后繼節(jié)點(diǎn)，只需1行代碼即可搞定：
p—>next = p—>next—>next;
但，若是刪除鏈表的最有一個(gè)節(jié)點(diǎn)（鏈表中只剩下這個(gè)節(jié)點(diǎn)），則代碼如下：
if(head—>next == null){
head = null;
}
從上面的情況可以看出，針對(duì)鏈表的插入、刪除操作，需要對(duì)插入第一個(gè)節(jié)點(diǎn)和刪除最后一個(gè)節(jié)點(diǎn)的情況進(jìn)行特殊處理。這樣代碼就會(huì)顯得很繁瑣，所以引入“哨兵”節(jié)點(diǎn)來解決這個(gè)問題。
3.引入“哨兵”的情況
“哨兵”節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，無論鏈表是否為空，head指針都會(huì)指向它，作為鏈表的頭結(jié)點(diǎn)始終存在。這樣，插入第一個(gè)節(jié)點(diǎn)和插入其他節(jié)點(diǎn)，刪除最后一個(gè)節(jié)點(diǎn)和刪除其他節(jié)點(diǎn)都可以統(tǒng)一為相同的代碼實(shí)現(xiàn)邏輯了。
4.“哨兵”還有哪些應(yīng)用場(chǎng)景？
這個(gè)知識(shí)有限，暫時(shí)想不出來呀！但總結(jié)起來，哨兵最大的作用就是簡(jiǎn)化邊界條件的處理。
四、重點(diǎn)留意邊界條件處理
經(jīng)常用來檢查鏈表是否正確的邊界4個(gè)邊界條件：
1.如果鏈表為空時(shí)，代碼是否能正常工作？
2.如果鏈表只包含一個(gè)節(jié)點(diǎn)時(shí)，代碼是否能正常工作？
3.如果鏈表只包含兩個(gè)節(jié)點(diǎn)時(shí)，代碼是否能正常工作？
4.代碼邏輯在處理頭尾節(jié)點(diǎn)時(shí)是否能正常工作？
五、舉例畫圖，輔助思考
核心思想：釋放腦容量，留更多的給邏輯思考，這樣就會(huì)感覺到思路清晰很多。
六、多寫多練，沒有捷徑
5個(gè)常見的鏈表操作：
1.單鏈表反轉(zhuǎn)
2.鏈表中環(huán)的檢測(cè)
3.兩個(gè)有序鏈表合并
4.刪除鏈表倒數(shù)第n個(gè)節(jié)點(diǎn)
5.求鏈表的中間節(jié)點(diǎn)
練習(xí)題LeetCode對(duì)應(yīng)編號(hào)：206，141，21，19，876。大家可以去練習(xí)，另外建議作者兄每章直接給出LC的題目編號(hào)或鏈接方便大家練習(xí)。
