上次我們學習了環形鏈表的數據結構，那麼接下來我們來一起看看下麵的問題， 判斷一個單向鏈表是否是環形鏈表？ 看到這個問題，有人就提出了進行遍歷鏈表，記住第一元素，當我們遍歷後元素再次出現則是說明是環形鏈表，如果沒有這是一個單向非環形鏈表。 我們來分析下上述的解決方法，我們分析這個程式的時間複雜度則是O ...
上次我們學習了環形鏈表的數據結構，那麼接下來我們來一起看看下麵的問題，
判斷一個單向鏈表是否是環形鏈表？
看到這個問題，有人就提出了進行遍歷鏈表，記住第一元素，當我們遍歷後元素再次出現則是說明是環形鏈表，如果沒有這是一個單向非環形鏈表。
我們來分析下上述的解決方法，我們分析這個程式的時間複雜度則是O(n)。 那麼是不是最優的選擇呢？
我們引入新的解決思路，那就是“快慢指針”。 我們來看看接下來的解決思路，是否比上面的思路有優化的地方。
思路： 當我們在遍歷鏈表的時候，我們設計兩個指針，分別是快指針和慢指針，塊指針每次走2步，而慢指針每次走1步，這樣的話在當我們兩個指針在鏈表中，如果會第二次相遇則說明這裡面的鏈表是環形鏈表。
我們來用代碼實現
|
/** * 查看 鏈表中是否存在環形 * * @return */ public boolean hasRing() {
if (head != null && size > 0) { Node<T> fastTemp = head, lowTemp = head;
while (lowTemp.getNext() != null && fastTemp.getNext() != null) { fastTemp = fastTemp.getNext().getNext(); lowTemp = lowTemp.getNext();
if (lowTemp == fastTemp) { return true; } } }
return false; } |
解析：定義了兩個指針節點 分別是 Node<T> fastTemp = head, lowTemp = head;
分別都是從head 開始 移動。那麼下一次項目的時候，則是快指針走了兩圈，慢指針走了一圈，所一下次相遇在原地位置。
接下來的問題就是我們在設計快慢指針的時候，是否必須是2倍速速的快慢指針。
如圖所示：
假設： 快慢指針在C點相遇，那麼相遇點在離迴圈點B之間是x 那麼頭節點A離B的距離為 k
在相遇的時候
慢指針：K + X + n*(X+Y) = m; ①
X+Y 繞環一圈的距離；n 慢指針 總共繞了幾圈在環內
快指針：
快指針是慢指針 速度的2倍，當它們相遇時 所用的時間是一樣的。那麼快指針 走過得距離是2*m;
K+X +N*(X+Y) = 2*m; ②
N為快指針繞過得圈數
將 ② - ① 得到下麵公式
(N-n)*(X+Y) = m;
接下將 ① 代入 上式得到
(N-n)*(X+Y) = K+X+n*(X+Y);
這裡X+Y 環長是個定值。 假設環長為M
(N-n)*M = K+X+n*M; ---- > 得出變形得到 K+X = (N-2*n)*M ;
公式 ：K+X = (N-2*n)*M
由於我們設計的是O型迴圈鏈表，那麼 起始就是迴圈點B上，則(N-2*n)*M = 0。
N = 2*n; 相遇時 快慢指針所繞 環的圈數 前者是後者的2倍，所用時間相同。這裡跟環有多少節點沒有關係。
上海尚學堂java培訓原作，陸續有數據機構等等java技術文章奉上，請多關註！
下麵看一個例子：
給定一個未知的長度的單向環形鏈表，如何確定鏈表中間位置的節點元素？
我們也可以使用“快慢指針”來實現，當快指針走一圈，然後停止，那麼慢指針的位置則是，中間元素的位置。此時的 時間複雜O(n) = 1/2 n
