環鍊表

從判斷一個單鍊表是否存在循環而擴展衍生的問題,有則稱之為有環鍊表問題。

產品簡介

鍊表在面試中出現的頻率很高,有的比較正常,考鍊表的常規操作,主要看基本功是否紮實,有些就比較難,難在思維的改變和是否能夠想到對應的點。這裡出現的是其中一個題目,我稱之為有環鍊表問題。也就是從判斷一個單鍊表是否存在循環而擴展衍生的問題。下面來看問題如何解決。

首先來看最基本的這個問題:如何判斷一個單鍊表是否存在循環,鍊表數目未知。算法不能破壞鍊表。

解決方法

第一種方法,將所有的遍歷過的節點用某個結構存儲起來,然後每遍歷一個節點,都在這個結構中查找是否遍歷過,如果找到有重複,則說明該鍊表存在循環;如果直到遍歷結束,則說明鍊表不存在循環。

這個結構我們可以使用hash來做,hash中存儲的值為節點的記憶體地址,這樣查找的操作所需時間為O(1),遍歷操作需要O(n),hash表的存儲空間需要額外的O(n)。所以整個算法的時間複雜度為O(n),空間複雜度為O(n)。

第二種方法,比較的特別,是使用反轉指針的方法,每過一個節點就把該節點的指針反向。

當有環的時候,最後指針會定位到鍊表的頭部,如果到最後,都沒有再到頭部,那說明鍊表不存在循環。

這個方法會破壞掉鍊表,所以如果要求是不能破壞鍊表的話,我們最後就還需要反轉一下,再將鍊表恢復。

這個方法使用的空間複雜度為O(1),其實是使用了3個指針,用於進行反轉。同時,時間複雜度為O(n)。

第三種方法,可能大家已經知道了,同時也是面試官大多想要得到的答案,就是快慢指針。

快指針pf(f就是fast的縮寫)每次移動2個節點,慢指針ps(s為slow的縮寫)每次移動1個節點,如果快指針能夠追上慢指針,那就說明其中有一個環,否則不存在環。

這個方法的時間複雜度為O(n),空間複雜度為O(1),實際使用兩個指針。

其實第三種解法存在問題,當一個存在環的鍊表足夠長,而環足夠小,那么會存在快指針永遠不會追上慢指針的情況。快慢指針只適用於環出現在鍊表尾部的情況,也就是單鍊表環的問題,而無法解決鍊表存在循環的問題。

相關詞條

熱門詞條

聯絡我們