作者：Jark；
鏈接：wuchong.me/blog/2014/03/25/interview-link-questions/
一文中總結了面試中幾個關於鏈表常見的面試題：O(1)時間刪除鏈表節點、單鏈錶轉置、求鏈表倒數第K個節點、求鏈表的中間節點。本文繼續總結其它常見的鏈表面試題如判斷鏈表是否有環、是否相交等等。
判斷單鏈表是否存在環
題目描述：輸入一個單向鏈表，判斷鏈表是否有環？
分析：通過兩個指針，分別從鏈表的頭節點出發，一個每次向後移動一步，另一個移動兩步，兩個指針移動速度不一樣，如果存在環，那麼兩個指針一定會在環裡相遇。
代碼：如下
找到環的入口點
題目描述：輸入一個單向鏈表，判斷鏈表是否有環。如果鏈表存在環，如何找到環的入口點？
分析：由上題可知，按照 p2 每次兩步，p1 每次一步的方式走，發現 p2 和 p1 重合，確定了單向鏈表有環路了。接下來，讓p2回到鏈表的頭部，重新走，每次步長不是走2了，而是走1，那麼當 p1 和 p2 再次相遇的時候，就是環路的入口了。
為什麼：假定起點到環入口點的距離為 a，p1 和 p2 的相交點M與環入口點的距離為b，環路的周長為L，當 p1 和 p2 第一次相遇的時候，假定 p1 走了 n 步。那麼有：p1走的路徑： a+b ＝ n；p2走的路徑： a+b+k*L = 2*n； p2 比 p1 多走了k圈環路，總路程是p1的2倍
根據上述公式可以得到 k*L=a+b=n顯然，如果從相遇點M開始，p1 再走 n 步的話，還可以再回到相遇點，同時p2從頭開始走的話，經過n步，也會達到相遇點M。
顯然在這個步驟當中 p1 和 p2 只有前 a 步走的路徑不同，所以當 p1 和 p2 再次重合的時候，必然是在鏈表的環路入口點上。
代碼：如下
判斷兩個鏈表是否相交
題目描述：給出兩個單向鏈表的頭指針（如下圖所示），判斷這兩個鏈表是否相交。這裡為了簡化問題，我們假設兩個鏈表均不帶環。
分析：
1、直接循環判斷第一個鏈表的每個節點是否在第二個鏈表中。但，這種方法的時間複雜度為O(Length(h1) * Length(h2))。顯然，我們得找到一種更為有效的方法，至少不能是O（N^2）的複雜度。
2、針對第一個鏈表直接構造hash表，然後查詢hash表，判斷第二個鏈表的每個節點是否在hash表出現，如果所有的第二個鏈表的節點都能在hash表中找到，即說明第二個鏈表與第一個鏈表有相同的節點。時間複雜度為為線性：O(Length(h1) + Length(h2))，同時為了存儲第一個鏈表的所有節點，空間複雜度為O(Length(h1))。是否還有更好的方法呢，既能夠以線性時間複雜度解決問題，又能減少存儲空間？
3、轉換為環的問題。把第二個鏈表接在第一個鏈表後面，如果得到的鏈表有環，則說明兩個鏈表相交。如何判斷有環的問題上面已經討論過了，但這裡有更簡單的方法。因為如果有環，則第二個鏈表的表頭一定也在環上，即第二個鏈表會構成一個循環鏈表，我們只需要遍歷第二個鏈表，看是否會回到起始點就可以判斷出來。這個方法的時間複雜度是線性的，空間是常熟。
4、進一步考慮“如果兩個沒有環的鏈表相交於某一節點，那麼在這個節點之後的所有節點都是兩個鏈表共有的”這個特點，我們可以知道，如果它們相交，則最後一個節點一定是共有的。而我們很容易能得到鏈表的最後一個節點，所以這成了我們簡化解法的一個主要突破口。那麼，我們只要判斷兩個鏈表的尾指針是否相等。相等，則鏈表相交；否則，鏈表不相交。
所以，先遍歷第一個鏈表，記住最後一個節點。然後遍歷第二個鏈表，到最後一個節點時和第一個鏈表的最後一個節點做比較，如果相同，則相交，否則，不相交。這樣我們就得到了一個時間複雜度，它為O((Length(h1) + Length(h2))，而且只用了一個額外的指針來存儲最後一個節點。這個方法時間複雜度為線性O(N)，空間複雜度為O(1)，顯然比解法三更勝一籌。
代碼：如下
兩個鏈表相交的第一個公共節點
題目描述：如果兩個無環單鏈表相交，怎麼求出他們相交的第一個節點呢？
分析：採用對齊的思想。計算兩個鏈表的長度 L1 , L2，分別用兩個指針 p1 , p2 指向兩個鏈表的頭，然後將較長鏈表的 p1（假設為 p1）向後移動L2 - L1個節點，然後再同時向後移動p1 , p2，直到 p1 = p2。相遇的點就是相交的第一個節點。
代碼：如下
擴展：鏈表有環，如何判斷相交
題目描述：上面的問題都是針對鏈表無環的，那麼如果現在，鏈表是有環的呢?上面的方法還同樣有效麼?
分析：如果有環且兩個鏈表相交，則兩個鏈表都有共同一個環，即環上的任意一個節點都存在於兩個鏈表上。因此，就可以判斷一鏈表上倆指針相遇的那個節點，在不在另一條鏈表上。
代碼：如下
擴展：兩鏈表相交的第一個公共節點
題目描述：如果兩個無環單鏈表相交，怎麼求出他們相交的第一個節點呢？
分析：採用對齊的思想。計算兩個鏈表的長度 L1 , L2，分別用兩個指針 p1 , p2 指向兩個鏈表的頭，然後將較長鏈表的 p1（假設為 p1）向後移動L2 - L1個節點，然後再同時向後移動p1 , p2，直到 p1 = p2。相遇的點就是相交的第一個節點。
代碼如下：
10. 總結
可以發現，在鏈表的問題中，通過兩個的指針來提高效率是很值得考慮的一個解決方案，所以一定要記住這種解題思路。記住幾種典型的鏈表問題解決方案，很多類似的題目都可以轉換到熟悉的問題再解決。
閱讀更多 javafirst 的文章
