以下是個(gè)人對(duì)所做過的LeetCode題中有關(guān)鏈表類型題的總結(jié)，博主小白啊，若有錯(cuò)誤的地方，請(qǐng)留言指出，謝謝。

一、有關(guān)反轉(zhuǎn)鏈表

反轉(zhuǎn)鏈表是在單鏈表題中占很大的比例，有時(shí)候，會(huì)以各種形式出現(xiàn)在題中，是比較重要的知識(shí)點(diǎn)。

?（1）題Reorder list中，思路為將鏈表一分為二，將后者反轉(zhuǎn)以后，然后兩鏈表交叉連接起來即可，這里值得注意的有：鏈表一分為二以后，前半段的鏈表最后要指向NULL，以形成兩單鏈表的交叉鏈接的情況；另外一點(diǎn)是，當(dāng)鏈表個(gè)數(shù)為奇數(shù)時(shí)，以快慢指針形式分割的鏈表，后半段的個(gè)數(shù)會(huì)多一個(gè)，所以，最后的時(shí)候，要判斷后半段是否結(jié)束。

（2）題Reverse linked list ii中要反轉(zhuǎn)鏈表中的一段，思路為：找到反轉(zhuǎn)的起始點(diǎn)和其前綴，然后根據(jù)需反轉(zhuǎn)的個(gè)數(shù)寫一個(gè)for循環(huán)，來實(shí)現(xiàn)反轉(zhuǎn)，這里用到的可以說是增加表頭的反轉(zhuǎn)（更多詳見反轉(zhuǎn)單鏈表）。這里值得注意的是，題中中給的范圍和結(jié)點(diǎn)的對(duì)應(yīng)。

（3）題Reverse nodes in k group?要以每K個(gè)結(jié)點(diǎn)為單位進(jìn)行反轉(zhuǎn)，思路為：先統(tǒng)計(jì)結(jié)點(diǎn)數(shù)，然后每K個(gè)結(jié)點(diǎn)進(jìn)行反轉(zhuǎn) ，這里使用的技巧是，使用計(jì)數(shù)器，當(dāng)num小于k時(shí)反轉(zhuǎn)。每次反轉(zhuǎn)結(jié)束，要更新前結(jié)點(diǎn)等。Swap nodes in pairs是上一題的當(dāng)K等于2時(shí)的特殊情況，不過，因?yàn)橹皇敲績蓚€(gè)進(jìn)行交換，所以不需要使用計(jì)數(shù)器，只要兩兩交換即可。

二、鏈表歸并排序

（1）Merge two sorted lists?合并兩鏈表，可以使用歸并排序的思想，每次從表頭取出值較小的結(jié)點(diǎn)，排到新鏈表中。這里值得注意的是，當(dāng)鏈表中有一個(gè)提前結(jié)束時(shí)，要將另一個(gè)的剩下的結(jié)點(diǎn)鏈接到新鏈表中。Sort list是歸并排序的鏈表實(shí)現(xiàn)。Merge k sorted lists?是對(duì)鏈表歸并排序的延續(xù)，這里有三種方法：一是先合并兩條，然后用新的去合并下一條，直到所有的都合并結(jié)束；二是鏈表兩兩合并，用形成的新鏈表列再兩兩合并，直到只剩下一條；三是使用優(yōu)先隊(duì)列，每次從隊(duì)列頭取出當(dāng)前值最小的節(jié)點(diǎn)，形成新的鏈表。

三、快慢指針

這里以快慢指針形式的還有Convert sorted list to binary search tree、Sort list?、Linked list cycle、Linked list cycle ii、還有幾題是快慢指針的另一種變形，總體來說，使用快慢指針的思想很重要。

（1）Linked list cycle、Linked list cycle ii都是快慢結(jié)點(diǎn)的應(yīng)用，關(guān)鍵在理解題意。判斷是否有環(huán)，看快慢指針是否相遇即可，找到環(huán)起點(diǎn)，只要在相遇點(diǎn)，一個(gè)放到鏈表表頭，一個(gè)從相遇點(diǎn)，兩者同步同速的走就行。

（2）Convert sorted list to binary search tree使用快慢指針找到根結(jié)點(diǎn)，然后遞歸實(shí)現(xiàn)就行。

四、刪除結(jié)點(diǎn)

（1）Remove duplicates from sorted list刪除重復(fù)結(jié)點(diǎn)，只保留一個(gè)重復(fù)結(jié)點(diǎn)，思路是，當(dāng)當(dāng)前結(jié)點(diǎn)cur和其next相等時(shí)，更新cur的next，不相等則cur前進(jìn)。Remove duplicate from sorted list ii是前一題的升級(jí)版，只要結(jié)點(diǎn)值有重復(fù)的都刪除，這時(shí)，因?yàn)榭赡軇h除頭結(jié)點(diǎn)，所以要新建一個(gè)表頭。思路：用前結(jié)點(diǎn)pre（初始為表頭的前綴）的next和當(dāng)前結(jié)點(diǎn)cur的next比較，若值相等，則cur前移，（是和cur->next比較而不是cur）這樣的做的原因是為了方便pre位置的下一次確定。只有當(dāng)pre和cur之間沒有重復(fù)的時(shí)pre才移動(dòng)，類似于1->2->3，pre為1，cur為2；當(dāng)之間有重復(fù)的時(shí)候，只是更新pre的后綴而已，然后再移動(dòng)cur繼續(xù)比較。

（2）題remove nth node from the end of list中要?jiǎng)h除指定的結(jié)點(diǎn)，這類題是快慢指針的另一種變形。思路：先快指針先走，然后快慢指針同時(shí)同速一塊走。

五、其他

（1）題Add two numbers?中，兩正整數(shù)以指針的形式表示，求其和，思路關(guān)鍵在于：對(duì)兩鏈表中有一個(gè)提前結(jié)束的理解，這里可以采取有就加，沒有就跳。另外一點(diǎn)是最高位的進(jìn)位值得注意。

（2）題Partition list中，要將小于給定值的結(jié)點(diǎn)放在不小于給定值結(jié)點(diǎn)之前，且保持相對(duì)順序不變。思路有幾種（這里介紹兩種）：一是找到第一個(gè)不小于給定值的結(jié)點(diǎn)及其前綴，然后從這個(gè)結(jié)點(diǎn)開始向后遍歷，將小于給定值的結(jié)點(diǎn)都插入到前綴和該結(jié)點(diǎn)之間（前綴要更新）

（3）Copy list with random pointer分三步，第一插入新結(jié)點(diǎn)，二調(diào)整random，三形成新鏈表。

轉(zhuǎn)載于:https://www.cnblogs.com/love-yh/p/7286192.html

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的Leetcode中单链表题总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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