目錄

技巧一：理解指針或者引用的含義

技巧二：警惕指針丟失和內(nèi)存泄漏

技巧三：利用哨兵簡(jiǎn)化實(shí)現(xiàn)難度

技巧四：重點(diǎn)留意邊界條件處理

技巧五：舉例畫圖，輔助思考

技巧六：多寫多練，沒有捷徑

---

鏈表的概念回顧：

頭結(jié)點(diǎn)和頭指針的區(qū)別

• 鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置叫做頭指針，那么整個(gè)鏈表的存取就必須是從頭指針開始進(jìn)行了。之后的每一個(gè)結(jié)點(diǎn)，其實(shí)就是上一個(gè)的后繼指針指向的位置。鏈?zhǔn)酱鎯?chǔ)時(shí)只要不是循環(huán)鏈表，就一定存在頭指針。
• 頭指針就是鏈表的名字。頭指針僅僅是個(gè)指針而已。頭結(jié)點(diǎn)是為了操作的統(tǒng)一與方便而設(shè)立的，放在第一個(gè)元素結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無意義（當(dāng)然有些情況下也可存放鏈表的長(zhǎng)度、用做監(jiān)視哨等等）。有了頭結(jié)點(diǎn)后，對(duì)在第一個(gè)元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，其操作與對(duì)其它結(jié)點(diǎn)的操作統(tǒng)一了
• 頭結(jié)點(diǎn)不是鏈表所必需的。
• 頭指針具有標(biāo)識(shí)作用，故常用頭指針冠以鏈表的名字。無論鏈表是否為空，頭指針均不為空。頭指針是鏈表的必要元素

寫鏈表代碼是最考驗(yàn)邏輯思維能力的。因?yàn)?#xff0c;鏈表代碼到處都是指針的操作、邊界條件的處理，稍有不慎就容易產(chǎn)生 Bug。鏈表代碼寫得好壞，可以看出一個(gè)人寫代碼是否夠細(xì)心，考慮問題是否全面，思維是否縝密。所以，這也是很多面試官喜歡讓人手寫鏈表代碼的原因

自己有決心并且付出精力是成功的先決條件，除此之外，我們還需要一些方法和技巧。分享幾個(gè)寫鏈表代碼技巧。

技巧一：理解指針或者引用的含義

• 不管是“指針”還是“引用”，實(shí)際上，它們的意思都是一樣的，都是存儲(chǔ)所指對(duì)象的內(nèi)存地址。
• 將某個(gè)變量賦值給指針，實(shí)際上就是將這個(gè)變量的地址賦值給指針，或者反過來說，指針中存儲(chǔ)了這個(gè)變量的內(nèi)存地址，指向了這個(gè)變量，通過指針就能找到這個(gè)變量

技巧二：警惕指針丟失和內(nèi)存泄漏

寫鏈表代碼的時(shí)候，指針指來指去，一會(huì)兒就不知道指到哪里了。所以，我們?cè)趯懙臅r(shí)候，一定注意不要弄丟了指針。

單鏈表的插入操作為例：

• 插入結(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)存泄漏
• 刪除結(jié)點(diǎn)時(shí)，一定要手動(dòng)釋放內(nèi)存

正確的插入操作：

x->next = p->next; // 將x的結(jié)點(diǎn)的next指針指向b結(jié)點(diǎn)； p->next = x; // 將p的next指針指向x結(jié)點(diǎn)；

技巧三：利用哨兵簡(jiǎn)化實(shí)現(xiàn)難度

單鏈表的插入和刪除操作分析：單鏈表的插入操作，第一個(gè)結(jié)點(diǎn)和其他結(jié)點(diǎn)的插入邏輯是不一樣的;

• 向一個(gè)空鏈表中插入第一個(gè)結(jié)點(diǎn)

if (head == null) {head = new_node; }

• 結(jié)點(diǎn) p 后面插入一個(gè)新的結(jié)點(diǎn)

new_node->next = p->next; p->next = new_node;

• 刪除結(jié)點(diǎn) p 的后繼結(jié)點(diǎn)

p->next = p->next->next;

• 刪除鏈表中的最后一個(gè)結(jié)點(diǎn)

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è)空鏈表嗎？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)的鏈表就叫作不帶頭鏈表。

帶頭鏈表的示意圖：

利用哨兵簡(jiǎn)化編程難度的技巧，在很多代碼實(shí)現(xiàn)中都有用到，比如插入排序、歸并排序、動(dòng)態(tài)規(guī)劃等。

技巧四：重點(diǎn)留意邊界條件處理

軟件開發(fā)中，代碼在一些邊界或者異常情況下，最容易產(chǎn)生 Bug。鏈表代碼也不例外。要實(shí)現(xiàn)沒有 Bug 的鏈表代碼，一定要在編寫的過程中以及編寫完成之后，檢查邊界條件是否考慮全面，以及代碼在邊界條件下是否能正確運(yùn)行：

檢查鏈表代碼是否正確的邊界條件有以下幾個(gè)：

• 如果鏈表為空時(shí)，代碼是否能正常工作？
• 如果鏈表只包含一個(gè)結(jié)點(diǎn)時(shí)，代碼是否能正常工作？
• 如果鏈表只包含兩個(gè)結(jié)點(diǎn)時(shí)，代碼是否能正常工作？
• 代碼邏輯在處理頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的時(shí)候，是否能正常工作？

實(shí)際上，不光光是寫鏈表代碼，你在寫任何代碼時(shí)，也千萬不要只是實(shí)現(xiàn)業(yè)務(wù)正常情況下的功能就好了，一定要多想想，你的代碼在運(yùn)行的時(shí)候，可能會(huì)遇到哪些邊界情況或者異常情況。遇到了應(yīng)該如何應(yīng)對(duì)，這樣寫出來的代碼才夠健壯！

技巧五：舉例畫圖，輔助思考

微復(fù)雜的鏈表操作，比如前面我們提到的單鏈表反轉(zhuǎn)，指針一會(huì)兒指這，一會(huì)兒指那，一會(huì)兒就被繞暈了。總感覺腦容量不夠，想不清楚。所以這個(gè)時(shí)候就要使用大招了，舉例法和畫圖法。

技巧六：多寫多練，沒有捷徑

精選了 5 個(gè)常見的鏈表操作。你只要把這幾個(gè)操作都能寫熟練，不熟就多寫幾遍，我保證你之后再也不會(huì)害怕寫鏈表代碼。

• 單鏈表反轉(zhuǎn)
• 鏈表中環(huán)的檢測(cè)
• 兩個(gè)有序的鏈表合并
• 刪除鏈表倒數(shù)第 n 個(gè)結(jié)點(diǎn)
• 求鏈表的中間結(jié)點(diǎn)

以上幾個(gè)操作的代碼后面更新補(bǔ)充

總結(jié)

以上是生活随笔為你收集整理的07 | 链表（下）：如何轻松写出正确的链表代码？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。