数据结构 | 如何一文搞定链表问题?(附20本书获奖名单)
這是本公號(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)操作包括但不局限于求鏈表長(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é)果。
????"""
????創(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é)果。
????"""?
????測(cè)試
????"""
????data?=?[1,?2,?3,?4,?5]????
????lst?=?LinkList()
????lst.InitList(data)
????lst.PrintList()
main()????
對(duì)應(yīng)的結(jié)果為:
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)即可。
????????"""
????????求取鏈表長(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)。代碼如下所示:
????"""
????刪除第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à)圖方便理解噢。
????"""
????把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
這里重要講解 2 個(gè)題型。
1.鏈表翻轉(zhuǎn)問(wèn)題
簡(jiǎn)單的說(shuō)就是將一個(gè)單鏈表翻轉(zhuǎn)過(guò)來(lái),這是 LeetCode 的第 206 題,在鏈表題目中很有分量。
輸出:5->4->3->2->1
這個(gè)題目其實(shí)不算難,思路比較清晰,只需要從前往后依次將結(jié)點(diǎn)指向顛倒,例如:
第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)行繪圖幫助理解,代碼如下:
????"""
????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
鏈表有環(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)題。
- 上一篇: 机器学习中如何处理不平衡数据?
- 下一篇: 重磅!这个 GitHub 汇总了 300