大家好，我是紀(jì)寧。
這篇文章將帶來(lái)完整版的鏈表內(nèi)容的講解。文章內(nèi)容包括鏈表的概念、分類、單雙鏈表的實(shí)現(xiàn)、鏈表的經(jīng)典OJ題目等。每一個(gè)專題中講解了相應(yīng)問(wèn)題實(shí)現(xiàn)思路及方法，當(dāng)然，實(shí)際解決過(guò)程中肯定也會(huì)出現(xiàn)各種各樣的小問(wèn)題，記錄每個(gè)問(wèn)題具體實(shí)現(xiàn)方法和代碼的文章鏈表在每個(gè)專題的末尾，點(diǎn)擊即可進(jìn)入。其次，文章末尾也提供了上述所有問(wèn)題鏈接的合集，供大家前往參考學(xué)習(xí)。

🧚什么是鏈表（鏈表概念及分類）

鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。非連續(xù)的意思就是鏈表的每一部分可以在內(nèi)存的任意一塊區(qū)域存在，且這塊區(qū)域的地址是隨機(jī)的，所以一般用動(dòng)態(tài)內(nèi)存來(lái)開(kāi)辟這塊空間的地址。而鏈表的每一部分都稱為一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)分為兩部分：數(shù)據(jù)域和指針域，通過(guò)指針域即可訪問(wèn)其他結(jié)點(diǎn)的數(shù)據(jù)。

鏈表分類

無(wú)頭單向非循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

單鏈表的每個(gè)節(jié)點(diǎn)分為兩部分，一部分存儲(chǔ)數(shù)據(jù)，一部分存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址。前一個(gè)節(jié)點(diǎn)中存儲(chǔ)著下一個(gè)節(jié)點(diǎn)的地址，這也是單鏈表能連起來(lái)的原因。
帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，但結(jié)構(gòu)最優(yōu)，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。

雙向鏈表的節(jié)點(diǎn)有兩個(gè)指針域和一個(gè)數(shù)據(jù)域，兩個(gè)指針一個(gè)指向后一個(gè)節(jié)點(diǎn)，另一個(gè)指向前一個(gè)節(jié)點(diǎn)，數(shù)據(jù)域中存儲(chǔ)數(shù)據(jù)。默認(rèn)雙向鏈表都是有帶哨兵位的頭節(jié)點(diǎn)，哨兵位的頭節(jié)點(diǎn)中儲(chǔ)存著第一個(gè)有效節(jié)點(diǎn)的地址（phead->next）和最后一個(gè)有效節(jié)點(diǎn)的地址（phead->prev）。 除了上面兩個(gè)最常用的鏈表之外，還有無(wú)頭單向循環(huán)鏈表、帶頭單向循環(huán)鏈表、帶頭單向不循環(huán)鏈表、無(wú)頭雙向循環(huán)鏈表等等，總之可以將是否帶頭、是否循環(huán)、單雙向這三個(gè)條件排列組合，另外還會(huì)有一些另類的復(fù)雜列表，文末會(huì)舉出例子。

單鏈表和雙鏈表的區(qū)別

單鏈表的指針域中只有一個(gè)地址，指向的是下一個(gè)結(jié)點(diǎn)的地址。而雙鏈表的指針域中有兩個(gè)地址：前一個(gè)結(jié)點(diǎn)的地址和后一個(gè)結(jié)點(diǎn)的地址。
單鏈表找尾結(jié)點(diǎn)比較麻煩，需要遍歷；而雙鏈表找尾結(jié)點(diǎn)只需要找頭結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)即可。
單鏈表只要一直往后遍歷就會(huì)遇到空指針結(jié)束，而雙向鏈表則可能會(huì)難以控制循環(huán)結(jié)束的條件而死循環(huán)下去。
單鏈表中一般默認(rèn)沒(méi)有哨兵位的頭結(jié)點(diǎn)；而雙鏈表中默認(rèn)頭結(jié)點(diǎn)，里面存的是最后一個(gè)結(jié)點(diǎn)和第一個(gè)有效結(jié)點(diǎn)的地址。

邏輯圖對(duì)比

物理圖對(duì)比

🚴?♂?單鏈表、雙向鏈表的實(shí)現(xiàn)

將鏈表中的數(shù)據(jù)類型重定義為某種類型，并定義一個(gè)鏈表節(jié)點(diǎn)的結(jié)構(gòu)體，其中節(jié)點(diǎn)的數(shù)據(jù)域是當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)，另一部分則是地址。即將鏈表的數(shù)據(jù)域和指針域放在一個(gè)結(jié)構(gòu)體中，且鏈表中存儲(chǔ)的數(shù)據(jù)最好是可變的，每生成一個(gè)鏈表都要單獨(dú)開(kāi)辟額外的空間。

單鏈表的實(shí)現(xiàn)

每開(kāi)辟一個(gè)結(jié)點(diǎn)的空間，都要為這個(gè)結(jié)點(diǎn)的數(shù)據(jù)域賦值，并讓它的指針域指向NULL。單鏈表的頭插頭刪都要傳二級(jí)指針，因?yàn)橐淖冾^插頭刪都要改變頭指針的指向，刪除某一結(jié)點(diǎn)，需要先找到這個(gè)結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)，必要時(shí)候要用另一個(gè)結(jié)點(diǎn)保存某個(gè)結(jié)點(diǎn)的地址，防止地址丟失的情況。
具體實(shí)現(xiàn)方式：單鏈表的實(shí)現(xiàn)

雙向鏈表的實(shí)現(xiàn)

雙向鏈表在開(kāi)辟結(jié)點(diǎn)時(shí)，要先將結(jié)點(diǎn)的指針域置空，當(dāng)確定結(jié)點(diǎn)位置時(shí)，再將結(jié)點(diǎn)的兩個(gè)指針域指向應(yīng)指向的結(jié)點(diǎn)。
具體實(shí)現(xiàn)方式：雙鏈表的實(shí)現(xiàn)

🍉鏈表經(jīng)典OJ筆試題

反轉(zhuǎn)單鏈表

思路是用三個(gè)指針，從前到后一次改變每個(gè)結(jié)點(diǎn)的指向。
題目及詳解：反轉(zhuǎn)單鏈表

移除鏈表元素

定義兩個(gè)指針，保證從第二個(gè)結(jié)點(diǎn)開(kāi)始，一個(gè)指針在另一個(gè)指針的后面，這樣就能在不丟失數(shù)據(jù)的情況下移除鏈表某結(jié)點(diǎn)。
題目及詳解：移除鏈表元素

合并兩個(gè)有序鏈表

將兩個(gè)鏈表的節(jié)點(diǎn)逐個(gè)比較，小的尾插到新鏈表的后面，每次尾插完，新鏈表和較小值的鏈表的指針都要向前走，有一個(gè)為空就停止循環(huán)，最后再將那個(gè)不為空的鏈表節(jié)點(diǎn)全部尾插到新鏈表。

這道題最好的思路是構(gòu)建一個(gè)哨兵位來(lái)實(shí)現(xiàn)尾插，不構(gòu)建哨兵位也可以，但需要考慮更多的邊界條件。
題目及詳解：合并兩個(gè)有序鏈表

鏈表分割

現(xiàn)有一鏈表的頭指針 ListNode* pHead，給一定值x，編寫(xiě)一段代碼將所有小于x的結(jié)點(diǎn)排在其余結(jié)點(diǎn)之前，且不能改變?cè)瓉?lái)的數(shù)據(jù)順序，返回重新排列后的鏈表的頭指針。
如圖，給定的鏈表為 4-5-3-1-2-7 ，給一定值為 3，分割后的值為 1-2-4-5-3-7

此題最好的解決方法是開(kāi)辟兩個(gè)哨兵位的頭結(jié)點(diǎn)，將這兩兩部分的數(shù)據(jù)按要求一次尾插到兩個(gè)哨兵位的后面，再將較小的一部分的尾結(jié)點(diǎn)指向較大部分的第一個(gè)結(jié)點(diǎn)，將較大部分的最后一個(gè)結(jié)點(diǎn)置空，最后將兩個(gè)哨兵位釋放，返回較小部分的第一個(gè)結(jié)點(diǎn)的地址即可。
題目及詳解：鏈表分割

鏈表的中間結(jié)點(diǎn)

給你單鏈表的頭結(jié)點(diǎn) head ，請(qǐng)你找出并返回鏈表的中間結(jié)點(diǎn)。如果有兩個(gè)中間結(jié)點(diǎn)，則返回第二個(gè)中間結(jié)點(diǎn)。
此題知識(shí)點(diǎn)：快慢指針
控制兩個(gè)指針，快指針每次向前走兩步步，慢指針每次向前走一步，當(dāng)快指針走到尾部的時(shí)候，慢指針則剛好走到中間結(jié)點(diǎn)。
題目及詳解：鏈表的中間結(jié)點(diǎn)

環(huán)形鏈表

環(huán)形鏈表中用到了快慢指針和追及問(wèn)題相關(guān)知識(shí)帶點(diǎn)。

環(huán)形鏈表 I：判斷鏈表中是否有環(huán)

環(huán)形鏈表 II：判斷鏈表開(kāi)始入環(huán)的第一個(gè)結(jié)點(diǎn)

環(huán)形鏈表I、II 題目及詳解：環(huán)形鏈表

復(fù)制帶隨機(jī)指針的鏈表

給你一個(gè)長(zhǎng)度為 n 的鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針 random ，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。構(gòu)造這個(gè)鏈表的 深拷貝。 深拷貝應(yīng)該正好由 n 個(gè) 全新 節(jié)點(diǎn)組成，其中每個(gè)新節(jié)點(diǎn)的值都設(shè)為其對(duì)應(yīng)的原節(jié)點(diǎn)的值。新節(jié)點(diǎn)的 next 指針和 random 指針也都應(yīng)指向復(fù)制鏈表中的新節(jié)點(diǎn)，并使原鏈表和復(fù)制鏈表中的這些指針能夠表示相同的鏈表狀態(tài)。復(fù)制鏈表中的指針都不應(yīng)指向原鏈表中的節(jié)點(diǎn)。

復(fù)制后的鏈表相關(guān)位置的索引必須和原鏈表一模一樣。
題目思路

• 拷貝所有節(jié)點(diǎn)，，每個(gè)結(jié)點(diǎn)放在對(duì)應(yīng)原節(jié)點(diǎn)的后面。
• 將每個(gè) random 指向?qū)?yīng)的位置。
• 將復(fù)制的鏈表解下來(lái)，尾插到一起，并將原鏈表恢復(fù)。

題目及詳解：復(fù)制帶隨機(jī)指針的鏈表

🥬鏈表相關(guān)文章直通車

單鏈表的實(shí)現(xiàn)
雙鏈表的實(shí)現(xiàn)
反轉(zhuǎn)單鏈表
移除鏈表元素
合并兩個(gè)有序鏈表
鏈表分割
鏈表的中間結(jié)點(diǎn)
環(huán)形鏈表
復(fù)制帶隨機(jī)指針的鏈表