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

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

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

鏈表分類

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

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

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

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

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

邏輯圖對比

物理圖對比

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

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

單鏈表的實現(xiàn)

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

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

雙向鏈表在開辟結(jié)點時，要先將結(jié)點的指針域置空，當確定結(jié)點位置時，再將結(jié)點的兩個指針域指向應指向的結(jié)點。
具體實現(xiàn)方式：雙鏈表的實現(xiàn)

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

反轉(zhuǎn)單鏈表

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

移除鏈表元素

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

合并兩個有序鏈表

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

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

鏈表分割

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

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

鏈表的中間結(jié)點

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

環(huán)形鏈表

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

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

環(huán)形鏈表 II：判斷鏈表開始入環(huán)的第一個結(jié)點

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

復制帶隨機指針的鏈表

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

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

• 拷貝所有節(jié)點，，每個結(jié)點放在對應原節(jié)點的后面。
• 將每個 random 指向?qū)奈恢谩?/li>
• 將復制的鏈表解下來，尾插到一起，并將原鏈表恢復。

題目及詳解：復制帶隨機指針的鏈表

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

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