4.3 雙指針

所謂雙指針是指利用兩個指針來解決與鏈表相關的面試題，這是一種常用思路。雙指針思路又可以根據兩個指針不同的移動方式細分成兩種不同的方法。第1種方法是前后雙指針，即一個指針在鏈表中提前朝著指向下一個節點的指針移動若干步，然后移動第2個指針。前后雙指針的經典應用是查找鏈表的倒數第k個節點。先讓第1個指針從鏈表的頭節點開始朝著指向下一個節點的指針先移動k-1步，然后讓第2個指針指向鏈表的頭節點，再讓兩個指針以相同的速度一起移動，當第1個指針到達鏈表的尾節點時第2個指針正好指向倒數第k個節點。

第2種方法是快慢雙指針，即兩個指針在鏈表中移動的速度不一樣，通常是快的指針朝著指向下一個節點的指針一次移動兩步，慢的指針一次只移動一步。采用這種方法，在一個沒有環的鏈表中，當快的指針到達鏈表尾節點的時候慢的指針正好指向鏈表的中間節點。

下面采用雙指針思路解決幾道典型的鏈表面試題。

面試題21：刪除倒數第k個節點

分析：如果可以遍歷鏈表兩次，那么這個問題就會變得簡單一些。在第1次遍歷鏈表時，可以得出鏈表的節點總數n。在第2次遍歷鏈表時，可以找出鏈表的第n-k個節點（即倒數第k+1個節點）。然后把倒數第k+1個節點的next指針指向倒數第k-1個節點，這樣就可以把倒數第k個節點從鏈表中刪除。

但題目要求只能遍歷鏈表一次。為了實現只遍歷鏈表一次就能找到倒數第k+1個節點，可以定義兩個指針。第1個指針P₁從鏈表的頭節點開始向前走k步，第2個指針P₂保持不動；從第k+1步開始指針P₂也從鏈表的頭節點開始和指針P₁以相同的速度遍歷。由于兩個指針的距離始終保持為k，當指針P₁指向鏈表的尾節點時指針P₂正好指向倒數第k+1個節點。

下面以在有6個節點的鏈表中找倒數第3個節點為例一步步分析這個過程。首先用第1個指針P₁從頭節點開始向前走2步到達第3個節點，如圖4.2（a）所示。然后初始化第2個指針P₂，讓它指向鏈表的頭節點，如圖4.2（b）所示。最后讓兩個指針同時向前遍歷，當指針P₁到達鏈表的尾節點時指針P₂剛好指向倒數第3個節點，如圖4.2（c）所示。

找出鏈表中倒數第3個節點之后再刪除倒數第2個節點比較容易，只需要把倒數第3個節點的next指針指向倒數第1個節點就可以。基于這種思路，可以編寫出如下所示的代碼：

由于當k等于鏈表的節點總數時，被刪除的節點為原始鏈表的頭節點，上述代碼的邏輯也可以簡化，運用哨兵節點來避免單獨處理刪除頭節點的情況。

面試題22：鏈表中環的入口節點

分析：解決這個問題的第1步是如何確定一個鏈表中包含環。如果一個鏈表中沒有環，那么自然不存在環的入口節點，此時應該返回null。

受到面試題21的啟發，仍可以用兩個指針來判斷鏈表中是否包含環。和解決前面的問題一樣，可以定義兩個指針并同時從鏈表的頭節點出發，一個指針一次走一步，另一個指針一次走兩步。如果鏈表中不包含環，走得快的指針直到抵達鏈表的尾節點都不會和走得慢的指針相遇。如果鏈表中包含環，走得快的指針在環里繞了一圈之后將會追上走得慢的指針。因此，可以根據一快一慢兩個指針是否能夠相遇來判斷鏈表中是否包含環。

? 需要知道環中節點數目的解法

第2步是如何找到環的入口節點，可以用兩個指針來解決。先定義兩個指針P₁和P₂，指向鏈表的頭節點。如果鏈表中的環有n個節點，第1個指針P₁先在鏈表中向前移動n步，然后兩個指針以相同的速度向前移動。當第2個指針P₂指向環的入口節點時，指針P₁已經圍繞環走了一圈又回到了入口節點。

下面以圖4.3中的鏈表為例來分析兩個指針的移動規律。指針P₁在初始化時指向鏈表的頭節點。由于環中有4個節點，指針P₁先在鏈表中向前移動4步到達第5個節點，如圖4.4（a）所示。然后將指針P₂指向鏈表的頭節點，如圖4.4（b）所示。接下來兩個指針以相同的速度在鏈表中向前移動直到相遇，它們相遇的節點正好是環的入口節點，如圖4.4（c）所示。

最后一個問題是如何得到環中節點的數目。前面在判斷鏈表中是否有環時用到了一快一慢兩個指針。如果兩個指針相遇，則表明鏈表中存在環。兩個指針之所以會相遇是因為快的指針繞環一圈追上慢的指針，因此它們相遇的節點一定是在環中。可以從這個相遇的節點出發一邊繼續向前移動一邊計數，當再次回到這個節點時就可以得到環中節點的數目。

下面的函數getNodeInLoop用一快一慢兩個指針找到環中的一個節點，如果鏈表中沒有環則返回null：

在找到環中任意一個節點之后，繞環一圈就能得出環中節點的數目，接下來再次使用雙指針就能找到環的入口節點。相應的代碼如下所示：

? 不需要知道環中節點數目的解法

上述代碼需要求出鏈表的環中節點的數目。如果仔細分析，就會發現其實并沒有必要求得環中節點的數目。如果鏈表中有環，快慢兩個指針一定會在環中的某個節點相遇。慢的指針一次走一步，假設在相遇時慢的指針一共走了k步。由于快的指針一次走兩步，因此在相遇時快的指針一共走了2k步。因此，到相遇時快的指針比慢的指針多走了k步。另外，兩個指針相遇時快的指針比慢的指針在環中多轉了若干圈。也就是說，兩個指針相遇時快的指針多走的步數k一定是環中節點的數目的整數倍，此時慢的指針走過的步數k也是環中節點數的整數倍。

此時可以讓一個指針指向相遇的節點，該指針的位置是之前慢的指針走了k步到達的位置。接著讓另一個指針指向鏈表的頭節點，然后兩個指針以相同的速度一起朝著指向下一個節點的指針移動，當后面的指針到達環的入口節點時，前面的指針比它多走了k步，而k是環中節點的數目的整數倍，相當于前面的指針在環中轉了k圈后也到達環的入口節點，兩個指針正好相遇。也就是說，兩個指針相遇的節點正好是環的入口節點。

簡化之后的代碼如下所示，和前面的代碼相比，此處省略了得到環中節點的數目的步驟：

面試題23：兩個鏈表的第1個重合節點

分析：很多應聘者都知道解決這個問題的蠻力法，即在第1個鏈表中順序遍歷每個節點，每遍歷到一個節點時，在第2個鏈表中順序遍歷每個節點。如果在第2個鏈表中有一個節點和第1個鏈表中的某個節點相同，則說明兩個鏈表在這個節點上重合，于是就找到了它們的公共節點。如果第1個鏈表的長度為m，第2個鏈表的長度為n，那么該方法的時間復雜度是O（mn）。

蠻力法通常不是最好的辦法，下面分析有公共節點的兩個鏈表有哪些特點，并從這些特點出發找出解決方法。

我們觀察到的第1個特點是，可以在重合的兩個鏈表的基礎上構造一個包含環的鏈表。以圖4.5中的兩個鏈表為例，首先從第2個鏈表的頭節點（值為7的節點）開始逐一遍歷鏈表中的節點直至到達尾節點（值為6的節點）。如果把尾節點的next指針連接到第2個鏈表的頭節點上，那么就可以構造出一個包含環的鏈表，如圖4.6所示。接下來只需要從第1個鏈表的頭節點開始找出環的入口節點（值為4的節點），該入口節點就是原來兩個鏈表的第1個重合節點。

前面已經詳細介紹了如何找出鏈表中環的入口節點，因此這里不再贅述。

我們觀察到的第2個特點是如果兩個鏈表有重合節點，那么這些重合節點一定只出現在鏈表的尾部。如果兩個單向鏈表有重合節點，那么從某個節點開始這兩個鏈表的next指針都指向同一個節點。在單向鏈表中，每個節點只有一個next指針，因此在第1個重合節點開始之后它們的所有節點都是重合的，不可能再出現分叉。

由于重合節點只可能出現在鏈表的尾部，因此可以從兩個鏈表的尾部開始向前比較，最后一個相同節點就是我們要找的節點。但是在單向鏈表中，只能從頭節點開始向后遍歷，直至到達尾節點。最后到達的尾節點卻要最先被比較，這就是通常所說的“后進先出”。至此不難想到可以用棧來解決這個問題：分別把兩個鏈表的節點放入兩個棧，這樣兩個鏈表的尾節點就位于兩個棧的棧頂。接下來比較兩個棧的棧頂節點是否相同。如果相同，則把棧頂節點彈出，然后比較下一個棧頂節點，直到找到最后一個相同的節點。

如果鏈表的長度分別為m和n，那么這種思路的時間復雜度是O（m+n）。上述思路需要用兩個輔助棧，因此空間復雜度也是O（m+n）。和最開始的蠻力法相比，這是一種用空間換時間的方法。

前面的解法之所以需要使用棧，是因為我們希望能同時到達兩個棧的尾節點。當兩個鏈表的長度不相同時，如果從頭開始遍歷，那么到達尾節點的時間就不一致。其實，解決這個問題還有一個更簡單的辦法：首先遍歷兩個鏈表得到它們的長度，這樣就能知道哪個鏈表比較長，以及長的鏈表比短的鏈表多幾個節點。在第2次遍歷時，第1個指針P₁在較長的鏈表中先移動若干步，再把第2個指針P₂初始化到較短的鏈表的頭節點，然后這兩個指針按照相同的速度在鏈表中移動，直到它們相遇。兩個指針相遇的節點就是兩個鏈表的第1個公共節點。

例如，在如圖4.5所示的兩個鏈表中，可以先各自遍歷一次，得到鏈表的長度，分別為6和5，也就是說較長的鏈表比較短的鏈表多1個節點。第2次先用一個指針P₁在長的鏈表中走1步，到達值為2的節點。接下來把指針P₂初始化到短的鏈表的頭節點（值為7的節點）。然后分別移動這兩個指針直到找到第1個相同的節點（值為6的節點），這就是我們想要的結果。這個過程如圖4.7所示。

理解這個過程之后就可以編寫出如下所示的Java代碼：

上述代碼將兩個鏈表分別遍歷兩次，第1次得到兩個鏈表的節點數，第2次找到兩個鏈表的第1個公共節點，這種方法的時間復雜度是O（m+n）。由于不需要保存鏈表的節點，因此這種方法的空間復雜度是O（1）。