單項鍊表查找、相交或成環的幾個算法

這篇文章介紹了單項鍊表上有關相交和成環的幾個問題和算法。

你也可以參考有關單項鍊表的另外幾篇文章：

單項鍊表實現的棧

反轉單項鍊表的四種算法

判斷兩個單項鍊表是否相交

問題描述

給定兩個單向鏈表，判斷鏈表是否相交（有共同的節點）。

算法一

最直接的解法，就是對其中一個鏈表（鏈表一）進行遍歷，在遍歷到每一個節點時，都在另一個鏈表（鏈表二）中進行遍歷，看是否有重複的節點，假設兩個鏈表的長度分別是 n 和 m，那麼最壞的漸進時間複雜度為 O (n * m)。

算法一的改進

凡是檢索節點均可能進行改進。算法一中存在對鏈表二的多次掃描檢索，可以採取以下思路進行簡化：

• 以空間換時間：使用標記數組將鏈表二中存在的值進行標記，然後遍歷鏈表一的時候，直接使用O (1) 的方法判斷是否在於鏈表二中。但這要求鏈表二的內容取值範圍較少或空間較大。簡化後，時間複雜度變為 O(n + m)，但空間複雜度較高。
• 將鏈表二的內容排序，利用二分查找減少查找時間，將空間複雜度降低為 O(nlog\[2\](m))。

注意：這裡所謂的「改進」有一個前提：節點的值不能重複。也就是說，重複節點值必須能夠代表同一個節點。

算法二

算法二的思路基於以下兩個原理：

• 兩個單向鏈表相交後，必然無法再分開。這是很容易想到的，因為只有一個方向，一旦有相同的節點，那麼後續的節點一定相同。
• 兩個單項鍊表相交後，尾節點一定相同。基於第一個原理，容易想到第二個。

於是，我們給出這樣的判斷：兩個鏈表相交，當且僅當兩個鏈表的尾元素相同：

1. 假設兩個鏈表相交，很容易證明兩個鏈表的尾元素是相同的。
2. 逆反命題：兩個鏈表的尾元素相同時，兩個鏈表一定相交。（注意：相同的節點不僅僅要求值相同，而是「同一個」，也就是指針地址相同。）

算法思路如下：

1. 遍歷鏈表一，找出尾節點指針。
2. 遍歷鏈表二，找出尾節點指針。
3. 如果兩個尾節點指針不為 nullptr 且相等，則兩個鏈表相交。

查找相交的兩個單向鏈表的第一個交點

這個問題是上面問題的擴展。通過觀察兩個相交鏈表的形狀（Y字形），我們可以看到，如果從尾部看，從尾部到第一個交點的這部分節點是「對齊」的，而前面的長度不同。我們讓前面也「右對齊」，這樣比較是否相交節點的時候，只需要對比一次而不是遍歷另一個節點。具體方法如下：

1. 找出兩個鏈表的長度 len1 和 len2. 假設 len1 > len2.
2. 讓長的鏈表先遍歷 len1 - len2 次。
3. 兩個鏈表一起遍歷，每次都判斷遍歷到的是否是同一個節點。

如果單項鍊表是有環的，那又該如何找到交點呢？

• 如果單項鍊表一個有環，一個沒環，那麼他們不可能相交；（因為有環之後，如果相交，則另一個一定也就有環了）
• 如果檢測兩個都有環（見下面的算法），那麼可以先找到環的起點，然後以此處為結束點，查找兩個鏈表到此位置的長度 len1 和 len2，然後再用上述方法來解決。

判斷單項鍊表是否有環

問題描述

給定一個單項鍊表，判斷鏈表中是否存在環。

算法一

遍歷單項鍊表，並對已經遍歷到的節點進行標記。每次遍歷的時候，從標記過的集合裡查找，如果找到相同節點，說明鏈表有環。時間複雜度為 O (n^2)。當然，也可以通過改進查找算法減少時間複雜度，但不會降低到 O (n)。

算法二

使用兩個指針同時遍歷鏈表。假設這兩個指針分別叫快指針 ptrFast 和慢指針 ptrSlow。

慢指針使用通常的方式遍歷：每次遍歷時有

ptrSlow = ptrSlow -> next;

快指針則以兩倍的速度遍歷：

ptrFast = ptrFast -> next;

設想：如果這個鏈表沒有環，就如同一條直直的公路，快的一方永遠不可能被慢的趕上。

但是，有環的時候，這種情況就不一樣了：

因為快的指針進入環中並且不停循環，快指針和慢指針將很快相遇。

這種方法的時間複雜度為 O(n)。

查找鏈表元素

問題描述

查找鏈表中指定的元素：

1. 找到鏈表中倒數第 k 個元素。
2. 找到鏈表的中間元素。

算法一

我們先從直觀上分析一下：要找到倒數第 k 個元素，必然要知道鏈表的長度，所以至少需要 O(n) 的時間。在不借助其他空間的情況下，此時我們無法反過來知道倒數第 k 個元素，因此必須重新遍歷，所以至少需要遍歷 2n - k 次。這種算法已經是很優秀的算法了，已經很難在不借助空間的情況下減少遍歷了。

算法二

這個算法只是更「優雅」，其實沒有變化：使用兩個指針 ptrFirst 和 ptrSecond。

對於第一個問題：讓兩個指針有 k 步的遍歷步距差值，這樣當第一個指針指向最後時，第二個指針正好指向倒數第 k 個。其實遍歷的次數和算法一相同。網上有一些文章誤認為這種方式更高效，其實沒有太本質的變化，只有常數的變化。

具體來說，就是先讓 ptrFirst 遍歷了 k 個節點後，兩個指針再開始一起遍歷節點。

同樣道理，對於第二個問題：讓 ptrFisrt 以兩倍的速度遍歷（參見本文上面的「快指針」和「慢指針」部分），當第一個指針遍歷到最後一個節點的時候，第二個指針正好遍歷到中點。

思考題：

1、如何找到鏈表 1/3 位置的節點？

2、如何找到單鏈表中環的起點和長度？（Tip：可以通過將單鏈表增加一維標記位，通過遍歷將標記位 域填充；如果發現有節點已經被填充該域，則說明有環；此時，這個點就是環的起點。時間複雜度 O(n)，空間複雜度 O(n)。）