這是本公號(hào)的第127篇原創(chuàng)。
近期看到一個(gè)數(shù)據(jù)結(jié)構(gòu)題目，翻轉(zhuǎn)鏈表。動(dòng)手寫(xiě)了下代碼，手生了不少，發(fā)現(xiàn)好鐵不用也會(huì)生銹，大腦也如此。
于是就整體回顧了一下鏈表的常見(jiàn)操作和數(shù)據(jù)結(jié)構(gòu)題，整理下分享出來(lái)，萬(wàn)一對(duì)讀者有幫助呢？想必那是極好的！目錄如下~

• 鏈表基礎(chǔ)知識(shí)

• 鏈表常見(jiàn)操作

• 鏈表常見(jiàn)題目

鏈表基礎(chǔ)知識(shí)

鏈表和順序表相對(duì)應(yīng)，順序表將表中的元素按照順序放置于連續(xù)的存儲(chǔ)區(qū)間，便于訪(fǎng)問(wèn)和查找。而鏈表則將元素放置于一系列結(jié)點(diǎn)中，各結(jié)點(diǎn)空間不要去連續(xù)，雖然給訪(fǎng)問(wèn)和查找?guī)?lái)了一定不便，但是在元素的刪除和插入等操作上有著得天獨(dú)厚的優(yōu)勢(shì)。（數(shù)組和鏈表結(jié)構(gòu)的在復(fù)雜度方面的優(yōu)缺點(diǎn)你get到了嗎？）

鏈表的結(jié)點(diǎn)包括數(shù)據(jù)域和指針域兩部分，顧名思義，數(shù)據(jù)域保存著元素的數(shù)據(jù)信息，指針域保存著下一個(gè)結(jié)點(diǎn)的指針標(biāo)識(shí)。當(dāng)然 Python 中沒(méi)有指針這個(gè)概念，刷題中也是模擬指針的概念進(jìn)行操作。

談到鏈表一定不能避開(kāi)的兩個(gè)定義：頭結(jié)點(diǎn)和頭指針。

頭結(jié)點(diǎn)的設(shè)立是為了便于操作，指的是放在第一個(gè)元素結(jié)點(diǎn)前的結(jié)點(diǎn)。不是鏈表結(jié)構(gòu)必不可少的一部分。頭指針則不一樣，屬于必不可少的一部分，指向鏈表結(jié)構(gòu)的第一個(gè)結(jié)點(diǎn)（頭結(jié)點(diǎn)存在的時(shí)候指向頭結(jié)點(diǎn)）。通常我們對(duì)鏈表的訪(fǎng)問(wèn)和各操作都是基于頭指針進(jìn)行的。

鏈表分類(lèi)則可以根據(jù)不同方式：

從內(nèi)存角度出發(fā)：?鏈表可分為 靜態(tài)鏈表、動(dòng)態(tài)鏈表。?

從鏈表存儲(chǔ)方式的角度出發(fā)： 鏈表可分為 單鏈表、雙鏈表、以及循環(huán)鏈表。

鏈表常見(jiàn)操作

鏈表的常見(jiàn)操作包括但不局限于求鏈表長(zhǎng)度、結(jié)點(diǎn)的刪除、插入等，但小詹之前文章說(shuō)過(guò)許多次，Python 中由于不存在指針，所以指針和鏈表指的都是模擬指針和鏈表。所以這里的常見(jiàn)操作應(yīng)當(dāng)加上鏈表的構(gòu)建操作。

1.首先是用 Python 構(gòu)建鏈表

如上所述，鏈表由一系列結(jié)點(diǎn)組成，所以構(gòu)建鏈表的第一步是定義一個(gè)結(jié)點(diǎn)類(lèi)。

class?Node(object):
????"""
????定義一個(gè)節(jié)點(diǎn)類(lèi)
????"""
????def?__init__(self,data):
????????self.data?=?data
????????self.next?=?None

有了結(jié)點(diǎn)，下一步就是構(gòu)建鏈表了。如下的 InitList() 方法用一個(gè)非空 data 構(gòu)建的鏈表，并定義了一個(gè) PrintList() 方法打印出鏈表結(jié)果。

class?LinkList(object):
????"""
????創(chuàng)建一個(gè)鏈表類(lèi)，包括判斷是否為空、打印鏈表
????"""
????def?__init__(self):
????????self.head?=?Node(None)?

????def?InitList(self,?data):
????????if?len(data)?==?0:
????????????print('\nIt?is?a?empty?link?list')
????????????return?False

????????self.head?=?Node(data[0])#頭結(jié)點(diǎn)，data的一個(gè)元素為數(shù)據(jù)域信息
????????p?=?self.head?#頭指針，指向第一個(gè)結(jié)點(diǎn)

????????for?i?in?data[1:]:
????????????node?=?Node(i)
????????????p.next?=?node
????????????p?=?p.next

????????def?IsEmpty(self):
????????p?=?self.head?#指向第一個(gè)結(jié)點(diǎn)

????def?IsEmpty(self):
????????p?=?self.head?#指向第一個(gè)結(jié)點(diǎn)????
????????if?p?==?None:
#???????????print('\nIt?is?a?empty?link?list')
????????????return?True?#是空鏈表????
#???????print('\nIt?is?not?empty')
????????return?False?#非空鏈表

????def?PrintList(self):
????????p?=?self.head

????????while?p:?#注意不是p.next
????????????print(p.data,?end?=?'?')?#end表示結(jié)束的標(biāo)識(shí)，不添加說(shuō)明時(shí)默認(rèn)為換行符
????????????p?=?p.next?????

這是一個(gè)簡(jiǎn)單的構(gòu)建鏈表方法并將其打印出來(lái)，可以測(cè)試下結(jié)果。

def?main():
????"""?
????測(cè)試
????"""
????data?=?[1,?2,?3,?4,?5]????
????lst?=?LinkList()
????lst.InitList(data)
????lst.PrintList()

main()????

對(duì)應(yīng)的結(jié)果為：

1?2?3?4?5???

2.其次是鏈表長(zhǎng)度的求取

鏈表長(zhǎng)度的求取在使用中經(jīng)常遇到，所以構(gòu)建了一個(gè)鏈表后，我們應(yīng)當(dāng)把一些常見(jiàn)的操作封裝到一起，為此，可以創(chuàng)建一個(gè)求表長(zhǎng)的方法，通過(guò)便歷鏈表所有結(jié)點(diǎn)即可。

def?Size(self):
????????"""
????????求取鏈表長(zhǎng)度
????????"""
????????p?=?self.head
????????size?=?0

????????while?p:
????????????size?+=?1
????????????p?=?p.next
????????return?size?

3.還有常見(jiàn)的結(jié)點(diǎn)刪除與插入

開(kāi)篇提到順序表對(duì)元素的查找和訪(fǎng)問(wèn)比較便捷，但是涉及到元素刪除和插入就比較雞肋了，鏈表中就相反，非常的便捷！

需要注意情況分類(lèi)，有大概 3 種情況。且刪除位置 n 應(yīng)當(dāng)有區(qū)間限制。

• 當(dāng)鏈表只有一個(gè)結(jié)點(diǎn)的時(shí)候

• 當(dāng)刪除的是第一個(gè)結(jié)點(diǎn)的時(shí)候

• 其他普適情況

對(duì)于第一種，只需要直接將頭結(jié)點(diǎn)為 None 即可；第二種情況和普適情況類(lèi)似，只是普適情況的前驅(qū)結(jié)點(diǎn)在第二種情況為頭結(jié)點(diǎn)。重點(diǎn)還在普適情況的刪除操作，可以簡(jiǎn)單的將前一個(gè)結(jié)點(diǎn)的指針指向待刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)即可跳過(guò)該結(jié)點(diǎn)。代碼如下所示：

def?Del(self,n):
????"""
????刪除第n個(gè)結(jié)點(diǎn)，注意特殊邊界情況
????"""
????if?self.IsEmpty()?or?n?<?0?or?n?>?self.Size():
????????print('error?occured')
????????return

????p?=?self.head?

????if?p.next?is?None:???#?當(dāng)只有一個(gè)節(jié)點(diǎn)的鏈表時(shí)
????????self.head?=?None
????????return????????

????if?n?==?1:???#?當(dāng)刪除第一個(gè)節(jié)點(diǎn)時(shí)
????????self.head?=?p.next
????????return

????#普通情況
????p?=?self.head????????
????index?=?1
????while?index?<?n:#找到要?jiǎng)h除的結(jié)點(diǎn)位置
????????pre?=?p
????????index?+=?1
????????p?=?p.next?????
??????pre.next?=?p.next#跳過(guò)該結(jié)點(diǎn)即可刪除
??????p?=?None

以上是刪除操作，考慮了各種刪除情況。插入操作和刪除有點(diǎn)類(lèi)似倒轉(zhuǎn)的感覺(jué)，只需要找到待插入位置，打斷前后兩個(gè)結(jié)點(diǎn)的指針，改變 3 者的指向關(guān)系即可。插入位置n范圍應(yīng)當(dāng)在閉區(qū)間（0，鏈表長(zhǎng)度）之間。值得注意的是這里也需要分情況討論，許多教程忽略了邊緣情況，這里著重討論下。

• 插入的鏈表為空鏈表

• 插入在鏈表的頭結(jié)點(diǎn)處

• 普適情況

前倆種情況類(lèi)似，只用將插入結(jié)點(diǎn)做頭結(jié)點(diǎn)即可，普適情況只需要將該結(jié)點(diǎn)的前后位置結(jié)點(diǎn)指針做些調(diào)整即可，代碼給出如下，可以手動(dòng)畫(huà)圖方便理解噢。

def?Insert(self,n,data):
????"""
????把data插入第n個(gè)結(jié)點(diǎn)之后的位置
????"""
????if?n?<?0?or?n?>?self.Size()?+?1:?
????#n最小值為0，且插入位置超過(guò)長(zhǎng)度+1時(shí)實(shí)際只能插入到最后，即最大值為鏈表長(zhǎng)【0，size】區(qū)間內(nèi)有效
????????print('error?occured')
????????return

????p?=?self.head

????if?self.IsEmpty():#空鏈表時(shí)插入頭指針之后即可
????????node?=?Node(data)
????????p.next?=?node
????????return

????if?n?==?0:
????????node?=?Node(data)
????????lat?=?self.head
????????self.head?=?node?#新插入的做頭結(jié)點(diǎn)
????????node.next?=?lat?#新插入結(jié)點(diǎn)后續(xù)指向之前的頭結(jié)點(diǎn)
????????return

????index?=?1
????while?index?<?n:
????????index?+=?1
????????p?=?p.next

????????#插入操作關(guān)鍵之處，注意指針變換順序
??????node?=?Node(data)
??????node.next?=?p.next
??????p.next?=?node

鏈表常見(jiàn)題目

這里重要講解 2 個(gè)題型。

1.鏈表翻轉(zhuǎn)問(wèn)題

簡(jiǎn)單的說(shuō)就是將一個(gè)單鏈表翻轉(zhuǎn)過(guò)來(lái)，這是 LeetCode 的第 206 題，在鏈表題目中很有分量。

輸入：1->2->3->4->5
輸出：5->4->3->2->1

這個(gè)題目其實(shí)不算難，思路比較清晰，只需要從前往后依次將結(jié)點(diǎn)指向顛倒，例如：

原?始：1->2->3->4->5
第1輪：5<-4??3->2->1
第2輪：5<-4<-3??2->1
第3輪：5<-4<-3<-2??1
第4輪：5<-4<-3<-2<-1

關(guān)鍵在于指針的轉(zhuǎn)換順序不能顛倒變換，建議自己按照我上邊給的示例進(jìn)行繪圖幫助理解，代碼如下：

class?Solution:
????"""
????leetcode題目中提交函數(shù)都只用放在此類(lèi)下
????"""
????def?reverseList(self,?head):
????????"""
????????翻轉(zhuǎn)操作leetcode題目206
????????"""
????????cur,?pre?=?head,?None
????????while?cur:
????????????cur.next,?pre,?cur?=?pre,?cur,?cur.next
????????????#這一行等同于如下?4?行：
????????????#lat?=?cur.next
????????????#cur.next?=?pre
????????????#pre?=?cur
????????????#cur?=?lat

????????return?pre

2.鏈表有環(huán)問(wèn)題（LeetCode第141題）

鏈表有環(huán)問(wèn)題也是一個(gè)常見(jiàn)的問(wèn)題了，之前在總結(jié)雙指針類(lèi)型問(wèn)題（見(jiàn)文末推薦閱讀）時(shí)候講過(guò)，可以去回顧下。思路如下：

• 定義兩個(gè)指針 ，一快一慢 。比如慢指針一次移動(dòng) 1 個(gè)位置 ，快指針移動(dòng) 2 個(gè) 。

• 初始快慢指針?lè)旁谝粋€(gè)位置 ，并開(kāi)始循環(huán)移動(dòng) 。

• 如果有環(huán) ，那么隨著移動(dòng)的進(jìn)行 ，終有快指針經(jīng)過(guò)環(huán)遇到并超過(guò)慢指針的時(shí)候 ，那么這就可以用來(lái)判斷是否存在環(huán)的依據(jù)啦 。

---

前幾天送的 20 本簽名書(shū)名單出來(lái)啦，恭喜這些 B 如此幸運(yùn)，快來(lái)看看有沒(méi)有你自己，如果沒(méi)有，繼續(xù)混臉熟，希望下一次就是你！記得添加微信領(lǐng)獎(jiǎng)（python_jiang），24小時(shí)后視作棄權(quán)噢~

名單：FavoreiteCheese；tj；阿飄-沖鋒版；明日之前；老孫9857；魏星；Nevermore陽(yáng)；部落大圣；D；mascot；微笑；Cosmos；飛；心雨；杜明羅；，。；陳偉；梅破知春近；寂夜；LuoYe；

推薦閱讀：

LeetCode 系列——雙指針問(wèn)題 。

LeetCode | 你不得不了解的哈希算法 ！

總結(jié)

以上是生活随笔為你收集整理的数据结构 | 如何一文搞定链表问题？（附20本书获奖名单）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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