背景
資料結構是我們程式設計師的基本功，無論是在日常工作還是在求職面試中都會經常用到；而且近年來程式設計師的工作競爭越來越大，資料結構和演算法在大廠的面試中都成了必考題。我所瞭解的：華為技術人員招聘必須先透過機試才能獲得面試機會，機試為兩道資料結構編碼題，每道題200分總分400，240分可透過。位元組跳動面試考察演算法是出名了的，不必多說。我所經歷的美團面試也都考察了資料結構和演算法。
由於我們的日常開發工作往往集中在業務邏輯程式碼的編寫，並且執行在Spring等優秀的框架之上，JDK的資料結構雖然熟練使用，但是對於底層邏輯及資料結構的瞭解少之又少，所以這就導致了面試中的資料結構與演算法題目變成了“送命題”。因此，我們開發人員在日常工作中需要多關注這些常用的資料結構、演算法，功夫用在平時，多積累，這樣在求職時才能夠得心應手。
問題最近有同事到某幾個大廠面試，都問到了連結串列相關的資料結構問題，比如單鏈表是否有環及環的入口檢測問題、單鏈表元素去重問題、單鏈表逆置問題等。我研究練習了“單鏈表是否有環及環的入口檢測問題”，作為日常積累，分享給大家。透過下圖，瞭解一下單鏈表有環和無環的兩種情況。
image.png
作為連結串列的第一篇，先看下如何構建連結串列。簡單起見，直接上程式碼（如下）。為了接下來演示方便，我提供了兩種連結串列的構建方式。第一種方式的目標是根據輸入的陣列從前往後建立單鏈表；第二種方式的目標是建立帶環的連結串列，帶環的依據是輸入的陣列序列中有且只有一個重複元素。
/** * 連結串列節點 */ public class Node { public Node(int data) { this.data = data; next = null; } public int data; public Node next; } /** * 構建連結串列（無環） */ private static Node buildLinklist(int[] texts) { Node head = new Node(0); Node node = head; for (int text : texts) { Node next = new Node(text); node.next = next; node = next; } return head; } /** * 構建連結串列，可能有環 */ private static Node buildCircleLinklist(int[] texts) { Node head = new Node(0); Node node = head; // 儲存已經建立過的節點 Map<Integer, Node> nodeMap = new HashMap<>(); for (int text : texts) { Node next = null; if (nodeMap.containsKey(text)) { next = nodeMap.get(text); } else { next = new Node(text); nodeMap.put(text, next); } node.next = next; node = next; } return head; }單鏈表是否有環及環的入口檢測問題，從題目可以知道，這其實是兩個問題。一是：檢測單鏈表中是否存在環；二是：如果存在環，則找到環的入口節點。所以，我們必須先解決第一個問題。
從頭節點遍歷連結串列，我們會發現：若連結串列中存在環，我們將無法找到連結串列的尾節點，一旦遍歷過程進入環，遍歷過程將在環內轉圈，永遠停不下來；若連結串列中不存在環，在有限的步驟內，我們的遍歷過程就會停止。所以，從連結串列遍歷的角度來看，我們可發現連結串列有環和無環的區別：
•無環：在有限步驟內，我們可以找到連結串列的尾節點，即：存在一個節點指向空地址。•有環：永遠無法找到尾節點，並且會在環內迴圈。
試想一下：如果我們的遍歷過程是有記憶的，記住所有走過的節點（從記憶體上來看每個節點都是唯一的），那麼我們會得出以下結論：
•無環：遍歷過程中從頭到尾每個節點都是不同的，上圖結果為：1-2-3-4-5-6-7-8-9-10-11；•有環：遍歷過程中，一旦進入環的迴圈過程，環內的節點將會重複出現，上圖結果為：1-2-3-4-5-6-7-8-9-10-11-4-5-6-7-8-9-10-11-4-5-6……。
所以，我就得出了今天的第一種解法，即：藉助輔助空間，儲存遍歷過程中所有經過的節點唯一資訊，每遍歷一個節點檢查其是否重複出現過，若遍歷過程結束也沒有發現重複節點，即可說明連結串列無環；若遍歷過程中出現節點重複時，即可說明連結串列有環，並且第一個重複的元素為環的入口。
補充說明一點：節點唯一資訊是透過Node物件的hashCode識別的，對於Node這個類，我並沒有重寫hashCode()方法，它代表的是物件的記憶體地址。
具體實現的程式碼如下所示：
/** * 檢查連結串列中是否有環：採用node唯一資訊，配合HashMap * * @param head 頭節點 * @return 若為空，則不存在環；不為空，則輸出為入口節點 */ private static Node detectCircleByExtraSpace(Node head) { // 用這個map儲存所有遍歷過的節點 Map<Integer, Node> nodeHashCodeMap = new HashMap<>(); Node node = head.next; // 節點不空則繼續遍歷，迴圈停止的條件有兩個：一是遍歷到連結串列尾節點，二是發現重複元素。 while (node != null) { // 獲取節點hashCode Integer hashCode = node.hashCode(); // 判斷是否曾經遍歷過 if (nodeHashCodeMap.containsKey(hashCode)) { // 如果曾經遍歷過，說明有環，並且這是入口 return node; } // 遍歷過即加入map nodeHashCodeMap.put(node.hashCode(), node); // 下一個 node = node.next; } // 走到這裡，就說明沒有環了。 return null; }接下來可以寫段程式碼進行測試，下面的例子使用序列“1, 2, 3, 4, 5, 6, 3”建立有環和無環兩種連結串列，結構如下圖所示；然後使用detectCircleByExtraSpace進行檢測。對於無環的應該輸出“無環”，對於有環的應該輸出“有環，入口為：3”。
image.png
public static void main(String[] args) { int[] texts = {1, 2, 3, 4, 5, 6, 3}; Node head = buildCircleLinklist(texts); Node node = detectCircleByExtraSpace(head); printResult(node); head = buildLinklist(texts); node = detectCircleByExtraSpace(head); printResult(node); } private static void printResult(Node node) { if (node == null) { System.out.println("無環"); } else { System.out.println("有環，入口為：" + node.data); } }上面的例子，輸出結果如下，符合預期。
有環，入口為：3無環熟悉這道題目的朋友，在看到題目時應該就想到了可以使用快慢指標來解決這個問題。一開始我只能理解檢測是否存在環這部分，對於入口檢測始終搞不明白，經過一陣公司推導，才弄清楚。這個解法的關鍵在於如何理解問題，以及理解問題後的一些數學公式推導。我試著說明一下快慢指標的解法原理。
首先看連結串列環的檢測。假如把帶環的連結串列比作一條單向的跑道，只能沿著箭頭方向跑，那麼跑步的人最終將會在環形跑道內轉圈。假設，甲乙兩人在沿跑道向相同的方向跑步，其中甲的速度是乙的速度的2倍；那麼，甲會先進入環形跑道一直繞圈，乙再進入環形跑道。甲乙都進入環形跑道後，就變成了行程問題中的“追及問題”，由於甲的速度大於乙，那麼在一段時間後甲肯定會追上乙的。當然，如果連結串列中沒有環，甲的速度大於乙，那麼甲會先跑到終點，過程中不會與乙相遇。
所以，我們可以使用上面“追及問題”的方式來解決連結串列環的檢測問題。設定兩個指標fast、slow，從連結串列頭部開始向後遍歷，fast的速度是slow的兩倍。如果fast能夠“追上”slow，則說明連結串列中存在環；若fast遍歷完成走到尾節點，則說明連結串列中不存在環。
然後分析如何找到環的入口。先說結論：如果連結串列中存在環，快慢指標相遇後，把fast指標移到連結串列頭部；然後fast和slow以相同的速度（每次移動一個節點）移動，當它們相遇時，相遇的點即為環的入口。再說如何推導，結合下圖進行說明：
先做幾個假設：
•假設從頭節點到環入口的距離為a，從環入口到fast、slow相遇點的距離為b，從相遇點到環入口的距離為c；•再假設連結串列的長度為L，環的長度為R；•假設slow走的距離為S，那麼fast走過的距離為2S（fast除了走過a+b外，可能還會繞環走n圈）。
那麼，就會有以下公式的推導：
最終得到：
結合上面說的結論（即：fast、slow相遇後，fast從頭節點開始移動，slow從相遇點繼續移動，fast的速度與slow一致），仔細看下這個公式代表了什麼？
•a代表了從頭節點到環入口的距離，相當於fast走過的距離；•c+(n-1)*R代表從slow從相遇點走到環入口後又沿著環走了n-1圈；•以上兩者相等即說明：fast、slow會在環的入口相遇；
所以：如果連結串列中存在環，快慢指標相遇後，把fast指標移到連結串列頭部；然後fast和slow以相同的速度（每次移動一個節點）移動，當它們相遇時，相遇的點即為環的入口。
以上就是快慢指標解法的原理過程，這麼看下來其實也是比較容易理解的。但是，如果沒有遇到過、聽說過，我是真的很難想到這個解法，尤其是第二步查詢環入口。好了，理論部分分析完了，我們看下程式碼該如何實現：
/** * 檢測連結串列是否有環，若有環則找到入口 * 使用快慢指標的方式 * * @param head 連結串列頭節點 * @return 若為空，則不存在環；不為空，則輸出為入口節點 */ private static Node detectCircleByFastSlow(Node head) { // 快慢指標從頭節點開始 Node fast = head; Node slow = head; // 用於記錄相遇點 Node encounter = null; // fast一次走兩步，所以要保證next和next.next都不為空，為空就說明無環 while (fast.next != null && fast.next.next != null) { // fast走兩步，slow走一步 fast = fast.next.next; slow = slow.next; // fast和slow一樣，說明相遇了，或者fast追上slow了。 if (fast == slow) { // 記錄相遇點，fast或slow都一樣 encounter = fast; // 相遇了，就退出環檢測過程 break; } } // 如果encounter為空，說明沒有環，就不用繼續找環入口了。 if (encounter == null) { return encounter; } // fast回到head位置 fast = head; // 只要兩者不相遇，就一直走下去 while (fast != slow) { // fast每次走一步，slow每次走一步，速度一樣 fast = fast.next; slow = slow.next; } // 相遇點，即為環入口 return fast; }修改上面的測試程式碼，會發現與解法一的結果一致。
public static void main(String[] args) { int[] texts = {1, 2, 3, 4, 5, 6, 3}; Node head = buildCircleLinklist(texts); Node node = detectCircleByFastSlow(head); printResult(node); head = buildLinklist(texts); node = detectCircleByFastSlow(head); printResult(node); }本文采用“輔助空間法”和“快慢指標法”兩種方式解決了判斷單鏈表是否有環及環入口查詢的經典問題，兩種方法各有利弊，簡單總結如下：
•輔助空間法：時間複雜度為O(n)，空間複雜度為O(n)。好處是容易想到，容易理解；壞處是會消耗額外的輔助空間；•快慢指標法：時間複雜度為O(n)，空間複雜度為O(1)。效能較好，但是不容易理解。
資料結構與演算法的重要性文章開頭已經說了，我還想再補充一些：雖然看起來很難，但是這些常見的問題、解法都是固定的，只要我們多積累、多練習、多思考，並且靈活運用到工作中去，就會發現它其實沒有想象中那麼難。
原文連結：https://mp.weixin.qq.com/s/Goit7IWF-zJzVTz-gkykkg?utm_source=tuicool&utm_medium=referral