鏈表

鏈表是數(shù)據(jù)結(jié)構(gòu)里一個很基礎(chǔ)但是又很愛考的線性結(jié)構(gòu)，鏈表的操作相對來說比較簡單，但是非常適合考察面試者寫代碼的能力，以及對 corner case 的處理，還有指針的應(yīng)用很容易引起 NPE (null pointer exception)。綜合以上原因，鏈表在面試中很重要。

提到鏈表就不得不提數(shù)組，它和數(shù)組可以說是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，那么它們最主要的區(qū)別在于：

•  數(shù)組在物理內(nèi)存上必須是連續(xù)的
•  鏈表在物理內(nèi)存上不需要連續(xù)，通過指針連接

所以數(shù)組最好的性質(zhì)就是可以隨機訪問 random access，有了 index，可以 O(1) 的時間訪問到元素。

而鏈表因為不連續(xù)，所以無法 O(1) 的時間定位任意一個元素的位置，那么就只能從頭開始遍歷。

這就造成了它們之間增刪改查上效率的不同。

除此之外，鏈表本身的結(jié)構(gòu)與數(shù)組也是完全不同的。

LinkedList 是由 ListNode 來實現(xiàn)的： 

class ListNode {  
  int value;  
  ListNode next;  
} 

結(jié)構(gòu)上長這樣：

這是單向鏈表，那還有的鏈表是雙向鏈表，也就是還有一個 previous pointer 指向當(dāng)前 node 的前一個 node： 

class ListNode {  
  int value;  
  ListNode next;  
  ListNode prev;  
} 

其實鏈表相關(guān)的題目沒有很難的，套路也就這么幾個，其中最?？甲罨A(chǔ)的題目是反轉(zhuǎn)鏈表，聽說微軟可以用這道題電面刷掉一半的 candidate，兩種方法一遍 bug free 還是不容易的。文章之前已經(jīng)寫過了，點擊這里直達(dá)復(fù)習(xí)。

今天我們來說鏈表中最主要的 2 個技巧：雙指針法和 dummy node，相信看完本文后，鏈表相關(guān)的絕大多數(shù)題目你都能搞定啦。

雙指針法

雙指針法在很多數(shù)據(jù)結(jié)構(gòu)和題型中都有應(yīng)用，在鏈表中用的最多的還是快慢指針。

顧名思義，兩個指針一個走得快，一個走得慢，這樣的好處就是以不同的速度遍歷鏈表，方便找到目標(biāo)位置。

常見的問題比如找一個鏈表的中點，或者判斷一個鏈表是否有環(huán)。

例 1：找中點

這題就是給一個鏈表，然后找到它的中點，如果是奇數(shù)個很好辦，如果是偶數(shù)個，題目要求返回第二個。

比如：

1 -> 2 -> 3 -> 4 -> 5 -> NULL，需要返回 3 這個 ListNode；

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL，需要返回 4 這個 ListNode。

但其實吐槽一下，如果真的要設(shè)計一個這樣的 API，我更傾向于選擇返回偶數(shù)個中的第一個中點。

為什么呢？

算法題都是工業(yè)生產(chǎn)中一些問題的抽象。比如說我們找中點的目的是為了把這個鏈表斷開，那么返回了 3，我可以斷開 3 和 4；但是返回了 4，單向鏈表我怎么斷開 4 之前的地方呢？還得再來一遍，麻煩。

Solution

方法一、

這題最直觀的解法就是可以先求這個鏈表的長度，然后再走這個長度的一半，得到中點。 

class Solution {  
    public ListNode middleNode(ListNode head) {  
        if(head == null) {  
          return null;  
        }  
        int len = 0;  
        ListNode current = head;  
        while(current != null) {  
            len++;  
            currentcurrent = current.next;  
        }  
        len /= 2;  
        ListNode result = head;  
        while(len > 0) {  
            resultresult = result.next;  
            len--;  
        }  
        return result;  
    }  
} 

方法二、快慢指針

我們用兩個指針一起來遍歷這個鏈表，每次快指針走 2 步，慢指針走 1 步，這樣當(dāng)快指針走到頭的時候，慢指針應(yīng)該剛好在鏈表的中點。 

class Solution {  
    public ListNode middleNode(ListNode head) {  
        ListNode slow = head;  
        ListNode fast = head;  
        while(fast != null && fast.next != null) {  
            slowslow = slow.next;  
            fastfast = fast.next.next;  
        }  
        return slow;  
    }  
} 

這兩個方法孰優(yōu)孰劣呢？

網(wǎng)上很多說什么方法一過了兩遍鏈表，方法二只過了一遍。

但其實，但是方法二用了兩個指針來遍歷，所以兩個方法過的遍數(shù)都是一樣的。

它們最大的區(qū)別是：

方法一是 offline algorithm，方法二是 online algorithm。

公司里的數(shù)據(jù)量是源源不斷的，比如電商系統(tǒng)里總有客戶在下單，社交軟件里的好友增長是一直在漲的，這些是數(shù)據(jù)流 data stream，我們是無法計算數(shù)據(jù)流的長度的。

那么 online algorithm 能夠給時刻給出當(dāng)前的結(jié)果，不用說等數(shù)據(jù)全部錄入完成后，實際上也錄不完。。這是 online algorithm 比 offline algorithm 大大的優(yōu)勢所在。

更多的解釋大家可以參考 stack overflow 的這個問題，鏈接在文末。

例 2：判斷單鏈表是否有環(huán)

思路：快慢指針一起從 head 出發(fā)，每次快指針走 2 步，慢指針只走 1 步，如果存在環(huán)，那么兩個指針一定會相遇。

這題是典型的龜兔賽跑，或者說在操場跑圈時，跑的快的同學(xué)總會套圈跑的慢的。 

public class Solution {  
    public boolean hasCycle(ListNode head) {  
        ListNode slow = head;  
        ListNode fast = head;  
        while(fast != null && fast.next != null) {  
            slowslow = slow.next;  
            fastfast = fast.next.next;  
            if(slow == fast) {  
                return true;  
            }  
        }  
        return false;  
    }  
} 

這題有個升級版，就是要求返回環(huán)的起點。

例 3：返回有環(huán)鏈表的環(huán)的起點

這題我感覺不全是個算法題了，還是個數(shù)學(xué)題哈哈。

先擺出結(jié)論：

1.  快慢指針從鏈表頭開始走，相遇的那點，記為 M；
2.  再用 2 個指針，一個從頭開始走，一個從 M 開始走，相遇點即為 cycle 的起點。

我們先看抽象出來的圖：

假設(shè)快慢指針在 M 點第一次相遇，

這里我們設(shè) 3 個變量來表示這個鏈表里的幾個重要長度：

•  X：從鏈表頭到環(huán)的起點的長度；
•  Y：從環(huán)的起點到 M 點的長度；
•  Z：從 M 點到環(huán)的起點的長度。

注意：因為環(huán)是有方向的，所以 Y 并不是 Z。

那其實我們唯一知道的關(guān)系就是：快慢指針在 M 點第一次相遇。這也是我們最初假設(shè)的關(guān)系。

而快慢指針有一個永遠(yuǎn)不變的真理：快指針走的長度永遠(yuǎn)是慢指針走的長度的 2 倍。

相遇時快慢指針分別走了多少的長度呢？

•  快指針：X+ Y + 假設(shè)走了 k 圈
•  慢指針：X + Y

那么我們就可以用這個 2 倍的關(guān)系，列出下列等式：

2 * (X + Y) = X + Y + kL

所以 X + Y = kL

而我們注意到：Y + Z = L，那么就能得出 X = Z。

所以當(dāng)兩個指針，一個從頭開始走，一個從 M 點開始走時，相遇那點就是環(huán)的起點，證畢。

來看下代碼吧： 

public class Solution {  
  public ListNode detectCycle(ListNode head) {  
    ListNode slow = head;  
    ListNode fast = head;  
    while (fast != null && fast.next != null) {  
      slowslow = slow.next;  
      fastfast = fast.next.next;  
​      if (slow == fast) {  
​        ListNode x = head; 
​        ListNode y = slow;  
​        while(x != y) {  
​          xx = x.next;  
​          yy = y.next;  
​        }  
​        return x;  
​      }  
​    }  
​    return null;  
  }  
} 

這題還有個應(yīng)用，就是找一個特定數(shù)組里重復(fù)的數(shù)字，這里就不展開了，大家感興趣的去做一下吧～

接下來我們聊聊 dummy node 這個技巧。

Dummy node

Dummy 的中文是“假”的意思，dummy node 大概可以翻譯成虛擬節(jié)點？有更地道的說法的話還請大家在評論區(qū)告訴我呀～

一般來說，dummy node 的用法是在鏈表的真實 head 的前面加一個指向這個 head 的節(jié)點，目的是為了方便操作 head。

對于鏈表來說，head 是一個鏈表的靈魂，因為無論是查詢還是其他的操作都需要從頭開始，俗話說擒賊先擒王嘛，抓住了一個鏈表的頭，就抓住了整個鏈表。

所以當(dāng)需要對現(xiàn)有鏈表的頭進行改動時，或者不確定頭部節(jié)點是哪個，我們可以預(yù)先加一個 dummyHead，這樣就可以靈活處理鏈表中的剩余部分，最后返回時去掉這個“假頭”就好了。

很多時候 dummy node 不是必須，但是用了會很方便，減少 corner case 的討論，所以還是非常推薦使用的。

光說不練假把式，我們直接來看題～

例 4：合并兩個排好序的鏈表

這題有很多種解法，比如最直觀的就是用兩個指針，然后比較大小，把小的接到最終的結(jié)果上去。

但是有點麻煩的是，最后的結(jié)果不知道到底誰是頭啊，是哪個鏈表的頭作為了最終結(jié)果的頭呢？

這種情況就非常適合用 dummy node。

先用一個虛擬的頭在這撐著，把整個鏈表構(gòu)造好之后，再把這個假的剔除。

來看代碼～ 

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 < l2.val) {  
​        ptr.next = l1;  
​        l1l1 = l1.next;  
​      } else {  
​        ptr.next = l2;  
​        l2l2 = l2.next;  
​      }  
​      ptrptr = ptr.next;  
​    }  
​    if (l1 == null) {  
​      ptr.next = l2; 
​    } else {  
​      ptr.next = l1;  
​    }  
​    return dummy.next;  
  }  
} 

這題也有升級版，就是合并 k 個排好序的鏈表。本質(zhì)上也是一樣的，只不過需要重寫一下比較器就好了。

例 5：刪除節(jié)點

這道題的意思是刪除鏈表中某個特定值的節(jié)點，可能有一個可能有多個，可能在頭可能在尾。

如果要刪除的節(jié)點在頭的時候，新鏈表的頭就不確定了，也有可能是個空的。。此時就很適合用 dummy node 來做，規(guī)避掉這些 corner case 的討論。

那這題的思路就是：用 2 個指針

•  prev：指向當(dāng)前新鏈表的尾巴
•  curr：指向當(dāng)前正在遍歷的 ListNode

如果 curr == 目標(biāo)值，那就直接移到下一個；

如果 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;  
​        prevprev = prev.next;  
​      }  
​      currcurr = curr.next;  
​    }  
​    prev.next = null;  
​    return dummy.next;  
  }  
} 

好了，以上就是本文的所有內(nèi)容了，如果這篇文章對你有幫助，歡迎分享給你身邊的朋友，也給齊姐點個「在看」，你們的支持是我創(chuàng)作的最大動力！

悄悄話

最近開通了視頻號，精力分散了許多，沒想到錄個 1 分鐘的短視頻也能這么多事。。

但是公眾號照常分享技術(shù)干貨和《齊姐聊大廠》系列，還請大家繼續(xù)關(guān)注支持呀，為了保證內(nèi)容的優(yōu)質(zhì)在線，可能準(zhǔn)備時間有點長，多謝大家的耐心等待～～如果想我了就來視頻號里找我玩～