主要參考文章地址 01.鏈表基礎(chǔ)知識(shí) | 算法通關(guān)手冊(cè) (itcharge.cn)）
本次內(nèi)容是對(duì)鏈表的總結(jié)，可以看了上面的文章之后。
在看我下面的內(nèi)容，做一個(gè)簡(jiǎn)短的復(fù)習(xí)，且本內(nèi)容的代碼均用C++實(shí)現(xiàn)，而參考資料的代碼則為python。
每一個(gè)標(biāo)題都有一個(gè)完整的鏈接，也可以點(diǎn)擊下面的鏈接。
單鏈表
雙鏈表
循環(huán)鏈表
內(nèi)核鏈表和企業(yè)鏈表
鏈表的排序
1 鏈表簡(jiǎn)介
鏈表的定義
一種線(xiàn)性表數(shù)據(jù)結(jié)構(gòu)。它使用一組任意的存儲(chǔ)單元，來(lái)存儲(chǔ)一組具有相同類(lèi)型的地址，但是鏈表一般是內(nèi)嵌到數(shù)據(jù)結(jié)構(gòu)中，而數(shù)據(jù)結(jié)構(gòu)的類(lèi)型可以是不同的。
2 單鏈表
優(yōu)缺點(diǎn)：
- 優(yōu)點(diǎn)：存儲(chǔ)空間不必事先分配；一些操作效率遠(yuǎn)比數(shù)組高（插入，移動(dòng)，刪除）
- 缺點(diǎn)：占用空間比數(shù)組多。
3 雙鏈表
簡(jiǎn)而言之，就是節(jié)點(diǎn)同時(shí)擁有前驅(qū)指針和后繼指針。使得使用更加的靈活
4 循環(huán)鏈表
簡(jiǎn)而言之，就是在雙鏈表的基礎(chǔ)上，末尾的后繼指針不在指向NULL，而是指向頭節(jié)點(diǎn)
5 內(nèi)核鏈表和企業(yè)鏈表
企業(yè)和內(nèi)核中使用鏈表，和我們常用的方式有所不同，如下所示，整體可以看作一個(gè)數(shù)據(jù)域，而指針域則內(nèi)嵌在數(shù)據(jù)域之中。
6 鏈表的排序
對(duì)于鏈表的排序算法，除了希爾排序之外，且堆排序不建議，其他排序方法都是支持的，如下：
冒泡排序，選擇排序，插入排序，歸并排序，快速排序，計(jì)數(shù)排序，桶排序和基數(shù)排序。
具體的算法可以參考上述鏈接。
7 鏈表的雙指針
雙指針（Two Pointers）：指的是在遍歷元素的過(guò)程中，不是使用單個(gè)指針進(jìn)行訪(fǎng)問(wèn)。
- 而是使用兩個(gè)指針進(jìn)行訪(fǎng)問(wèn)，從而達(dá)到相應(yīng)的目的。如果兩個(gè)指針?lè)较蛳喾?，則稱(chēng)為「對(duì)撞時(shí)針」。
- 如果兩個(gè)指針?lè)较蛳嗤?，則稱(chēng)為「快慢指針」。
- 如果兩個(gè)指針?lè)謩e屬于不同的數(shù)組 / 鏈表，則稱(chēng)為「分離雙指針」。
對(duì)撞指針
對(duì)于單鏈表而言，是不能夠反向指的，所以一般不會(huì)用到對(duì)撞指針?？赡軐?duì)于循環(huán)鏈表，可以嘗試使用兩個(gè)指針朝著不同的方向進(jìn)行移動(dòng)。
- 適用范圍：一般是在有序的數(shù)據(jù)結(jié)構(gòu)中使用。
快慢指針
起點(diǎn)不一致的快慢指針
顧名思義，就是兩個(gè)指針的起點(diǎn)不一樣，然后他們的速度可以是一樣的。
快指針fast比慢指針slow先走n步，知道快指針移動(dòng)到鏈表尾端為止。
- 比如你要定位到單向鏈表的指針最后一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，那么你就需要兩個(gè)指針，且前一個(gè)指針先走1步。
步長(zhǎng)不一致的快慢指針
步長(zhǎng)不一致，比如fast指針每次移動(dòng)2步，慢指針每次移動(dòng)一步，這樣就可以得到鏈表數(shù)據(jù)中間的節(jié)點(diǎn)。可以借此實(shí)現(xiàn)二分法查找。
還可以用來(lái)判斷鏈表是否成環(huán)問(wèn)題。
分離雙指針
這里最簡(jiǎn)單的例子就是鏈表在執(zhí)行歸并排序的時(shí)，就需要將左，右兩個(gè)鏈表進(jìn)行合并，就需要兩個(gè)分離指針進(jìn)行鏈表合并。
總結(jié)：
因?yàn)榈?點(diǎn)的內(nèi)容不多，這里不涉及刷題，所以第7點(diǎn)就直接總結(jié)了。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-608507.html
剩下的詳細(xì)內(nèi)容，可以在鏈接中看到。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-608507.html
到了這里，關(guān)于C++數(shù)據(jù)結(jié)構(gòu)之鏈表（詳解）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
