有關(guān)鏈表的小技巧，我都給你總結(jié)好了
鏈表
鏈表是數(shù)據(jù)結(jié)構(gòu)里一個(gè)很基礎(chǔ)但是又很愛(ài)考的線性結(jié)構(gòu)，鏈表的操作相對(duì)來(lái)說(shuō)比較簡(jiǎn)單，但是非常適合考察面試者寫(xiě)代碼的能力，以及對(duì) corner case 的處理，還有指針的應(yīng)用很容易引起 NPE (null pointer exception)。綜合以上原因，鏈表在面試中很重要。
提到鏈表就不得不提數(shù)組，它和數(shù)組可以說(shuō)是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，那么它們最主要的區(qū)別在于：
數(shù)組在物理內(nèi)存上必須是連續(xù)的 鏈表在物理內(nèi)存上不需要連續(xù)，通過(guò)指針連接
所以數(shù)組最好的性質(zhì)就是可以隨機(jī)訪問(wèn) random access，有了 index，可以 O(1) 的時(shí)間訪問(wèn)到元素。
而鏈表因?yàn)椴贿B續(xù)，所以無(wú)法 O(1) 的時(shí)間定位任意一個(gè)元素的位置，那么就只能從頭開(kāi)始遍歷。
這就造成了它們之間增刪改查上效率的不同。
除此之外，鏈表本身的結(jié)構(gòu)與數(shù)組也是完全不同的。
LinkedList 是由 ListNode 來(lái)實(shí)現(xiàn)的：
class?ListNode?{
??int?value;
??ListNode?next;
}
結(jié)構(gòu)上長(zhǎng)這樣：
這是單向鏈表，那還有的鏈表是雙向鏈表，也就是還有一個(gè) previous pointer 指向當(dāng)前 node 的前一個(gè) node：
class?ListNode?{
??int?value;
??ListNode?next;
??ListNode?prev;
}
其實(shí)鏈表相關(guān)的題目沒(méi)有很難的，套路也就這么幾個(gè)，其中最?？甲罨A(chǔ)的題目是反轉(zhuǎn)鏈表，聽(tīng)說(shuō)微軟可以用這道題電面刷掉一半的 candidate，兩種方法一遍 bug free 還是不容易的。文章之前已經(jīng)寫(xiě)過(guò)了，點(diǎn)擊這里直達(dá)復(fù)習(xí)。
今天我們來(lái)說(shuō)鏈表中最主要的 2 個(gè)技巧：雙指針?lè)?/strong>和 dummy node，相信看完本文后，鏈表相關(guān)的絕大多數(shù)題目你都能搞定啦。
雙指針?lè)?/span>
雙指針?lè)ㄔ诤芏鄶?shù)據(jù)結(jié)構(gòu)和題型中都有應(yīng)用，在鏈表中用的最多的還是快慢指針。
顧名思義，兩個(gè)指針一個(gè)走得快，一個(gè)走得慢，這樣的好處就是以不同的速度遍歷鏈表，方便找到目標(biāo)位置。
常見(jiàn)的問(wèn)題比如找一個(gè)鏈表的中點(diǎn)，或者判斷一個(gè)鏈表是否有環(huán)。
例 1：找中點(diǎn)
這題就是給一個(gè)鏈表，然后找到它的中點(diǎn)，如果是奇數(shù)個(gè)很好辦，如果是偶數(shù)個(gè)，題目要求返回第二個(gè)。
比如：
1 -> 2 -> 3 -> 4 -> 5 -> NULL，需要返回 3 這個(gè) ListNode；
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL，需要返回 4 這個(gè) ListNode。
但其實(shí)吐槽一下，如果真的要設(shè)計(jì)一個(gè)這樣的 API，我更傾向于選擇返回偶數(shù)個(gè)中的第一個(gè)中點(diǎn)。
為什么呢？
算法題都是工業(yè)生產(chǎn)中一些問(wèn)題的抽象。比如說(shuō)我們找中點(diǎn)的目的是為了把這個(gè)鏈表斷開(kāi)，那么返回了 3，我可以斷開(kāi) 3 和 4；但是返回了 4，單向鏈表我怎么斷開(kāi) 4 之前的地方呢？還得再來(lái)一遍，麻煩。
Solution
方法一、
這題最直觀的解法就是可以先求這個(gè)鏈表的長(zhǎng)度，然后再走這個(gè)長(zhǎng)度的一半，得到中點(diǎn)。
class?Solution?{
????public?ListNode?middleNode(ListNode?head)?{
????????if(head?==?null)?{
??????????return?null;
????????}
????????int?len?=?0;
????????ListNode?current?=?head;
????????while(current?!=?null)?{
????????????len++;
????????????current?=?current.next;
????????}
????????len?/=?2;
????????ListNode?result?=?head;
????????while(len?>?0)?{
????????????result?=?result.next;
????????????len--;
????????}
????????return?result;
????}
}
方法二、快慢指針
我們用兩個(gè)指針一起來(lái)遍歷這個(gè)鏈表，每次快指針走 2 步，慢指針走 1 步，這樣當(dāng)快指針走到頭的時(shí)候，慢指針應(yīng)該剛好在鏈表的中點(diǎn)。
class?Solution?{
????public?ListNode?middleNode(ListNode?head)?{
????????ListNode?slow?=?head;
????????ListNode?fast?=?head;
????????while(fast?!=?null?&&?fast.next?!=?null)?{
????????????slow?=?slow.next;
????????????fast?=?fast.next.next;
????????}
????????return?slow;
????}
}
這兩個(gè)方法孰優(yōu)孰劣呢？
網(wǎng)上很多說(shuō)什么方法一過(guò)了兩遍鏈表，方法二只過(guò)了一遍。
但其實(shí)，但是方法二用了兩個(gè)指針來(lái)遍歷，所以兩個(gè)方法過(guò)的遍數(shù)都是一樣的。
它們最大的區(qū)別是：
方法一是 offline algorithm，方法二是 online algorithm。
公司里的數(shù)據(jù)量是源源不斷的，比如電商系統(tǒng)里總有客戶在下單，社交軟件里的好友增長(zhǎng)是一直在漲的，這些是數(shù)據(jù)流 data stream，我們是無(wú)法計(jì)算數(shù)據(jù)流的長(zhǎng)度的。
那么 online algorithm 能夠給時(shí)刻給出當(dāng)前的結(jié)果，不用說(shuō)等數(shù)據(jù)全部錄入完成后，實(shí)際上也錄不完。。這是 online algorithm 比 offline algorithm 大大的優(yōu)勢(shì)所在。
更多的解釋大家可以參考 stack overflow 的這個(gè)問(wèn)題[1]，鏈接在文末。
例 2：判斷單鏈表是否有環(huán)
思路：快慢指針一起從 head 出發(fā)，每次快指針走 2 步，慢指針只走 1 步，如果存在環(huán)，那么兩個(gè)指針一定會(huì)相遇。
這題是典型的龜兔賽跑，或者說(shuō)在操場(chǎng)跑圈時(shí)，跑的快的同學(xué)總會(huì)套圈跑的慢的。
public?class?Solution?{
????public?boolean?hasCycle(ListNode?head)?{
????????ListNode?slow?=?head;
????????ListNode?fast?=?head;
????????while(fast?!=?null?&&?fast.next?!=?null)?{
????????????slow?=?slow.next;
????????????fast?=?fast.next.next;
????????????if(slow?==?fast)?{
????????????????return?true;
????????????}
????????}
????????return?false;
????}
}
這題有個(gè)升級(jí)版，就是要求返回環(huán)的起點(diǎn)。
例 3：返回有環(huán)鏈表的環(huán)的起點(diǎn)
這題我感覺(jué)不全是個(gè)算法題了，還是個(gè)數(shù)學(xué)題哈哈。
先擺出結(jié)論：
快慢指針從鏈表頭開(kāi)始走，相遇的那點(diǎn)，記為 M； 再用 2 個(gè)指針，一個(gè)從頭開(kāi)始走，一個(gè)從 M 開(kāi)始走，相遇點(diǎn)即為 cycle 的起點(diǎn)。
我們先看抽象出來(lái)的圖：
假設(shè)快慢指針在 M 點(diǎn)第一次相遇，
這里我們?cè)O(shè) 3 個(gè)變量來(lái)表示這個(gè)鏈表里的幾個(gè)重要長(zhǎng)度：
X：從鏈表頭到環(huán)的起點(diǎn)的長(zhǎng)度； Y：從環(huán)的起點(diǎn)到 M 點(diǎn)的長(zhǎng)度； Z：從 M 點(diǎn)到環(huán)的起點(diǎn)的長(zhǎng)度。
注意：因?yàn)榄h(huán)是有方向的，所以 Y 并不是 Z。
那其實(shí)我們唯一知道的關(guān)系就是：快慢指針在 M 點(diǎn)第一次相遇。這也是我們最初假設(shè)的關(guān)系。
而快慢指針有一個(gè)永遠(yuǎn)不變的真理：快指針走的長(zhǎng)度永遠(yuǎn)是慢指針走的長(zhǎng)度的 2 倍。
相遇時(shí)快慢指針?lè)謩e走了多少的長(zhǎng)度呢？
快指針：X+ Y + 假設(shè)走了 k 圈 慢指針：X + Y
那么我們就可以用這個(gè) 2 倍的關(guān)系，列出下列等式：
2 * (X + Y) = X + Y + kL
所以 X + Y = kL
而我們注意到：Y + Z = L，那么就能得出 X = Z。
所以當(dāng)兩個(gè)指針，一個(gè)從頭開(kāi)始走，一個(gè)從 M 點(diǎn)開(kāi)始走時(shí)，相遇那點(diǎn)就是環(huán)的起點(diǎn)，證畢。
來(lái)看下代碼吧：
public?class?Solution?{
??public?ListNode?detectCycle(ListNode?head)?{
????ListNode?slow?=?head;
????ListNode?fast?=?head;
????while?(fast?!=?null?&&?fast.next?!=?null)?{
??????slow?=?slow.next;
??????fast?=?fast.next.next;
??????if?(slow?==?fast)?{
????????ListNode?x?=?head;
????????ListNode?y?=?slow;
????????while(x?!=?y)?{
??????????x?=?x.next;
??????????y?=?y.next;
????????}
????????return?x;
??????}
????}
????return?null;
??}
}
這題還有個(gè)應(yīng)用，就是找一個(gè)特定數(shù)組里重復(fù)的數(shù)字，這里就不展開(kāi)了，大家感興趣的去做一下吧～
接下來(lái)我們聊聊 dummy node 這個(gè)技巧。
Dummy node
Dummy 的中文是“假”的意思，dummy node 大概可以翻譯成虛擬節(jié)點(diǎn)？有更地道的說(shuō)法的話還請(qǐng)大家在評(píng)論區(qū)告訴我呀～
一般來(lái)說(shuō)，dummy node 的用法是在鏈表的真實(shí) head 的前面加一個(gè)指向這個(gè) head 的節(jié)點(diǎn)，目的是為了方便操作 head。
對(duì)于鏈表來(lái)說(shuō)，head 是一個(gè)鏈表的靈魂，因?yàn)闊o(wú)論是查詢還是其他的操作都需要從頭開(kāi)始，俗話說(shuō)擒賊先擒王嘛，抓住了一個(gè)鏈表的頭，就抓住了整個(gè)鏈表。
所以當(dāng)需要對(duì)現(xiàn)有鏈表的頭進(jìn)行改動(dòng)時(shí)，或者不確定頭部節(jié)點(diǎn)是哪個(gè)，我們可以預(yù)先加一個(gè) dummyHead，這樣就可以靈活處理鏈表中的剩余部分，最后返回時(shí)去掉這個(gè)“假頭”就好了。
很多時(shí)候 dummy node 不是必須，但是用了會(huì)很方便，減少 corner case 的討論，所以還是非常推薦使用的。
光說(shuō)不練假把式，我們直接來(lái)看題～
例 4：合并兩個(gè)排好序的鏈表
這題有很多種解法，比如最直觀的就是用兩個(gè)指針，然后比較大小，把小的接到最終的結(jié)果上去。
但是有點(diǎn)麻煩的是，最后的結(jié)果不知道到底誰(shuí)是頭啊，是哪個(gè)鏈表的頭作為了最終結(jié)果的頭呢？
這種情況就非常適合用 dummy node。
先用一個(gè)虛擬的頭在這撐著，把整個(gè)鏈表構(gòu)造好之后，再把這個(gè)假的剔除。
來(lái)看代碼～
class?Solution?{
??public?ListNode?mergeTwoLists(ListNode?l1,?ListNode?l2)?{
????if?(l1?==?null)?{
??????return?l2;
????}
????if?(l2?==?null)?{
??????return?l1;
????}
????ListNode?dummy?=?new?ListNode(0);
????ListNode?ptr?=?dummy;
????while?(l1?!=?null?&&?l2?!=?null)?{
??????if?(l1.val?????????ptr.next?=?l1;
????????l1?=?l1.next;
??????}?else?{
????????ptr.next?=?l2;
????????l2?=?l2.next;
??????}
??????ptr?=?ptr.next;
????}
????if?(l1?==?null)?{
??????ptr.next?=?l2;
????}?else?{
??????ptr.next?=?l1;
????}
????return?dummy.next;
??}
}
這題也有升級(jí)版，就是合并 k 個(gè)排好序的鏈表。本質(zhì)上也是一樣的，只不過(guò)需要重寫(xiě)一下比較器就好了。
例 5：刪除節(jié)點(diǎn)
這道題的意思是刪除鏈表中某個(gè)特定值的節(jié)點(diǎn)，可能有一個(gè)可能有多個(gè)，可能在頭可能在尾。
如果要?jiǎng)h除的節(jié)點(diǎn)在頭的時(shí)候，新鏈表的頭就不確定了，也有可能是個(gè)空的。。此時(shí)就很適合用 dummy node 來(lái)做，規(guī)避掉這些 corner case 的討論。
那這題的思路就是：用 2 個(gè)指針
prev：指向當(dāng)前新鏈表的尾巴 curr：指向當(dāng)前正在遍歷的 ListNode
如果 curr == 目標(biāo)值，那就直接移到下一個(gè)；
如果 curr != 目標(biāo)值，那就把 prev 指向它，接上。
這題需要注意的是，最后一定要把 prev.next 指向 null，否則如果原鏈表的尾巴是目標(biāo)值的話，還是去不掉。
代碼如下：
class?Solution?{
??public?ListNode?removeElements(ListNode?head,?int?val)?{
????ListNode?dummy?=?new?ListNode(0);
????ListNode?prev?=?dummy;
????ListNode?curr?=?head;
????while(curr?!=?null)?{
??????if?(curr.val?!=?val)?{
????????prev.next?=?curr;
????????prev?=?prev.next;
??????}
??????curr?=?curr.next;
????}
????prev.next?=?null;
????return?dummy.next;
??}
}