鏈表是一種基本數(shù)據(jù)結(jié)構(gòu)，因?yàn)殒湵硎褂眠^(guò)程中指來(lái)指去的指針讓大家抓狂诚隙，以至于大家面試前總是要特意看下鏈表相關(guān)知識(shí)。今天鹰服，我來(lái)帶大家學(xué)習(xí)「鏈表」（Linked list) 這個(gè)數(shù)據(jù)結(jié)構(gòu)变屁。
我們總是拿鏈表和數(shù)組來(lái)進(jìn)行比較眼俊，不同于數(shù)組需要連續(xù)內(nèi)存意狠，鏈表并不需要一塊連續(xù)的內(nèi)存粟关，它通過(guò)「指針」將一組零散的內(nèi)存塊串聯(lián)起來(lái)使用。
了解了鏈表的官方定義后环戈，我們來(lái)看看鏈表有那些結(jié)構(gòu)闷板。鏈表包括單鏈表、循環(huán)鏈表院塞、雙向鏈表遮晚、雙向循環(huán)鏈表、靜態(tài)鏈表拦止。我們先來(lái)看最簡(jiǎn)單县遣、最常用的單鏈表。
鏈表通過(guò)指針將一組零散的內(nèi)存塊串聯(lián)起來(lái)汹族。其中萧求，內(nèi)存塊稱(chēng)為鏈表的「結(jié)點(diǎn)」。為了將所有結(jié)點(diǎn)串起來(lái)顶瞒，每個(gè)鏈表的結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外夸政，還需要記錄鏈上的下一個(gè)結(jié)點(diǎn)位置的指針漓踢。對(duì)于單鏈表更胖，我們把記錄下一個(gè)結(jié)點(diǎn)位置的指針叫做后繼指針 next。
從我給你的單鏈表插圖我們可以看出第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)比較特殊碧查。它們分別被稱(chēng)為頭結(jié)點(diǎn)和尾節(jié)點(diǎn)坑资。頭結(jié)點(diǎn)用來(lái)記錄鏈表的基地址耗帕，我們可以遍歷得到整條鏈表。而尾節(jié)點(diǎn)的指針不是指向下一個(gè)結(jié)點(diǎn)袱贮，而是指向一個(gè)空地址 Null兴垦，表示這是鏈表上最后一個(gè)結(jié)點(diǎn)。
對(duì)于鏈表的插入和刪除操作字柠，由于只涉及前后結(jié)點(diǎn)指針的改變探越，所以對(duì)應(yīng)的時(shí)間復(fù)雜度為 O(1)。但是窑业，鏈表要是想要隨機(jī)訪(fǎng)問(wèn)第 k 個(gè)元素就沒(méi)那么簡(jiǎn)單了钦幔，和數(shù)組靠尋址公式隨機(jī)訪(fǎng)問(wèn)不同。我們需要根據(jù)指針遍歷得到相應(yīng)結(jié)點(diǎn)常柄。
其實(shí)鏈表相當(dāng)于一個(gè)隊(duì)伍鲤氢，隊(duì)伍里面的每一個(gè)人只知道自己的前面一個(gè)人和后面一個(gè)人搀擂，當(dāng)我們?nèi)フ夷硞€(gè)人時(shí)，需要從第一個(gè)人往后數(shù)來(lái)找到某個(gè)特定的人卷玉。所以鏈表隨機(jī)訪(fǎng)問(wèn)第 k 個(gè)元素的時(shí)間復(fù)雜度是 O(n)哨颂。
循環(huán)鏈表其實(shí)就是一種特殊的單鏈表。單鏈表的尾節(jié)點(diǎn)指向 null相种。循環(huán)鏈表的尾節(jié)點(diǎn)指向頭結(jié)點(diǎn)威恼，就像貪吃蛇吃了自己的尾巴一樣，形成了一個(gè)環(huán)寝并。所以我們管它叫循環(huán)鏈表箫措。循環(huán)鏈表適用于解決約瑟夫問(wèn)題。
雙向鏈表不同于單向鏈表只有一個(gè) next 指針指向后面的結(jié)點(diǎn)衬潦，雙向鏈表不只有一個(gè) next 指針指向后面的結(jié)點(diǎn)斤蔓，還有一個(gè)前驅(qū)指針 prev 指向前面的結(jié)點(diǎn)。
那么單鏈表和雙向鏈表到底有什么區(qū)別呢镀岛？我舉鏈表的刪除操作給你舉例弦牡。
在實(shí)際的軟件開(kāi)發(fā)中鏈表的刪除操作無(wú)外這非兩種情況：
- 刪除結(jié)點(diǎn)中「值等于某個(gè)給定值」的結(jié)點(diǎn)；
- 刪除給定指針指向的結(jié)點(diǎn)漂羊。
對(duì)于第一種情況驾锰，單鏈表和雙鏈表都需要從頭結(jié)點(diǎn)開(kāi)始遍歷對(duì)比，直到找到等于給定值的結(jié)點(diǎn)拨与，然后通過(guò)指針操作將其刪除稻据。
單純的刪除操作時(shí)間復(fù)雜度是 O(1)，但遍歷查找結(jié)點(diǎn)的時(shí)間是主要耗時(shí)點(diǎn)买喧，對(duì)應(yīng)的時(shí)間復(fù)雜度為 O(n)捻悯。根據(jù)時(shí)間時(shí)間度的加法原則，刪除操作的時(shí)間復(fù)雜度為 O(n)淤毛。這種情況兩種鏈表沒(méi)有多大區(qū)別今缚。
第二種情況則不一樣，我們已經(jīng)知道了給定的結(jié)點(diǎn)了低淡，對(duì)于單鏈表來(lái)說(shuō)姓言，假設(shè)要?jiǎng)h除的結(jié)點(diǎn)為 q, 我們還要知道 q 的前驅(qū)結(jié)點(diǎn) p，我們還是要遍歷鏈表蔗蹋，直到 p->q何荚，找到 p 結(jié)點(diǎn)。對(duì)于雙向鏈表情況則有所不同猪杭，我們已經(jīng)有了記錄前驅(qū)結(jié)點(diǎn)的前驅(qū)指針 prev餐塘，所以我們執(zhí)行刪除操作的時(shí)間復(fù)雜度為 O(1)≡硭保看出來(lái)了吧戒傻，在刪除給定指針指向的結(jié)點(diǎn)的情況下税手，我們選擇雙向鏈表存儲(chǔ)數(shù)據(jù)在 O(1) 的時(shí)間復(fù)雜度下就搞定了！而單鏈表需要 O(n) 的時(shí)間復(fù)雜度需纳。
同理芦倒，對(duì)于在鏈表的某個(gè)特定結(jié)點(diǎn) q 前插入一個(gè)新的結(jié)點(diǎn)，雙向鏈表執(zhí)行插入操作的時(shí)間復(fù)雜度為 O(1)不翩。而單鏈表則為 O(n)兵扬。你可以自己分析一下原因。
對(duì)于有序鏈表慌盯，雙向鏈表的查詢(xún)效率也高于單鏈表周霉。因?yàn)槲覀兛梢陨洗尾樵?xún)的結(jié)點(diǎn) p, 每次查找時(shí)掂器，我們決定往前查找還是往后查亚皂，所以平均只需要一半的數(shù)據(jù)。
學(xué)習(xí)完了鏈表的基礎(chǔ)知識(shí)国瓮，下面我們進(jìn)入重點(diǎn)灭必，講解面試中常考的鏈表相關(guān)知識(shí)乃摹。
單鏈表反轉(zhuǎn)禁漓，合并有序鏈表，檢測(cè)鏈表中是否有環(huán)孵睬。這些都是高頻考點(diǎn)播歼，今天我?guī)阒饌€(gè)擊破。
在開(kāi)始上代碼前掰读，我?guī)懔私庀聦?xiě)鏈表代碼的基礎(chǔ)知識(shí)秘狞。
我們知道指針存儲(chǔ)了變量的內(nèi)存地址，指向了這個(gè)變量蹈集，我們通過(guò)這個(gè)指針就能找到這個(gè)變量烁试。
上面這段話(huà)可能有點(diǎn)拗口，沒(méi)關(guān)系拢肆，我們這樣理解减响。我們寫(xiě)鏈表時(shí)，經(jīng)常會(huì)寫(xiě) p->next = q郭怪。這是指 p 結(jié)點(diǎn)的 next 指針存儲(chǔ)了 q 結(jié)點(diǎn)的內(nèi)存地址支示，也就是 p 指向了 q。類(lèi)似的還有 p->next = p->next->next鄙才。這句代碼的意思是我們刪除了結(jié)點(diǎn) p 的后繼結(jié)點(diǎn)（即 p 后面的那個(gè)結(jié)點(diǎn)）颂鸿。因?yàn)槲覀儼?p 結(jié)點(diǎn)的 next 指針指向了存儲(chǔ) p 結(jié)點(diǎn)的下下一個(gè)結(jié)點(diǎn)的內(nèi)存地址。
好吧咒循，你可能看完之后更暈了据途。你可以返回去多看幾遍绞愚，還可以在紙上畫(huà)出來(lái)。我用的是 C 語(yǔ)言的指針概念颖医，沒(méi)學(xué)過(guò)的同學(xué)把它理解成 Java 的引用位衩。
在寫(xiě)鏈表代碼時(shí)我們重點(diǎn)要留意邊界條件，主要是空鏈表和只有一個(gè)結(jié)點(diǎn)的鏈表熔萧，我們的代碼是否還能正常工作糖驴。
好了，激動(dòng)人心的時(shí)刻來(lái)了佛致，上代碼吧贮缕！
單鏈表反轉(zhuǎn)：
我用的是 Java 語(yǔ)言實(shí)現(xiàn)的，用其他語(yǔ)言的同學(xué)不用害怕俺榆，思路都是一樣的感昼，我會(huì)加上注釋的。
public static Node reverse(Node head) {
Node previousNode = null;
Node headNode = null; // 要返回的新的頭結(jié)點(diǎn)
Node currentNode = head; // 頭結(jié)點(diǎn)指向 currentNode
while(currentNode != null) {
Node Next = currentNode.next; // 當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
// 如果下一個(gè)結(jié)點(diǎn)指向 null罐脊， 我們把當(dāng)前結(jié)點(diǎn)給 headNode定嗓，返回 headNode。
if( Next == null ) { headNode = currentNode; }
currentNode.next = previousNode;
previousNode = currentNode;
currentNode = Next;
} return headNode;
}
單鏈表中檢測(cè)是否有環(huán)
public boolean checkCircle(Node head) {
// 邊界條件
if(head == null || head.next == null ) { return false; }
// 快慢指針萍桌，如果有環(huán)宵溅，在環(huán)內(nèi)結(jié)點(diǎn)相遇，即 slow == fast
Node fast = head;
Node slow = head;
while(fast != null && fast.next != null ) {
fast = fast.next.next;
slow = slow.next;
if( slow == fast) {
return true; }
}
return false;
}
有序鏈表合并
public static Node merge(Node p1, Node p2) {
// 還是邊界條件上炎，面試中檢查邊界條件特別重要恃逻，切記。
if( p1 == null) { return p2; }
if(p2 == null ) { return p1; }
// 確定頭結(jié)點(diǎn)
Node p = p1;
Node q = p2;
Node headNode;
if(p.data < q.data ) {
headNode = p;
p = p.next;
} else {
headNode = q;
q = q.next;
}
// 結(jié)點(diǎn) r 穿針引線(xiàn)把新的有序鏈表連起來(lái)藕施。
Node r = headNode;
while( p != null && q != null) {
if( p.data < q.data) {
r.next = p;
p = p.next;
} else {
r.next = q;
q = q.next;
}
// 做出一輪比較后寇损，更新 r 結(jié)點(diǎn)。
r = r.next;
}
// 把剩下的結(jié)點(diǎn)連起來(lái)
if(q != null )
{
r.next = q;
} else {
r.next = p; }
return headNode;
}
好了铅碍，如果你能看懂并且把我上面的三個(gè)鏈表操作寫(xiě)熟練润绵，熟能生巧，我保證你不會(huì)再害怕手寫(xiě)鏈表了胞谈。
最后留一個(gè)思考題：在如何檢測(cè)環(huán)的基礎(chǔ)上尘盼，給一個(gè)鏈表，若其中包含環(huán)烦绳，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)卿捎，否則，輸出null径密。思考一下午阵，在評(píng)論區(qū)給我答案。
對(duì)你有幫助的話(huà)，給我個(gè)喜歡底桂！
