列表 環 判定 初始位置

判定的方法比較簡單 有兩種方法  

第1種是使用哈希表來存貯每個節點 這樣的話 當hashset[ ] 中出現兩個相同的節點時就能夠判斷出來這是1樣的了  然后他所在的那個位置就是環第1次出現的位置上

第2種方法是用兩個快慢指針來做  

設定兩個指針分別為p1  p2   ，  p1的移動速度為每次移動1個距離   ，而p2的移動速度為每次移動兩個距離  ，這樣 ，直到快指針到達鏈表的結尾位置 

如果如果兩個指針相遇的話  ，那就說明這個鏈表中存在環   ，沒有相遇的話就沒有存在環

可以想象  ，直到兩個指針相遇，慢指針在環內的移動距離是不會超過環的長度 ，那極限來講 如果鏈表是首尾相連的  那末 慢指針的移動距離正好為連表的長度  ，如果是1個小環的話，  那末 快指針也能夠在慢指針沒有走滿半個圓環的時間內追上慢指針。

下面來討論如何肯定初始位置的問題  設 連表出發點到環的初始位置的距離為a   p1和p2交點到環初始的位置為c （即p1在環內的移動距離為c） 環的長度為r  所以 對p1來講  他所走過的路成為X = a + c   對p2來講 他所走過的路程為       2X = a + c + k*r  （k的之不肯定 為自然數） 所以  x = k*r        如果讓慢指針再走X步的話 他照舊會回到p1 與 p2相交的那個點  如果 讓p2從連表的出發點開始走的話  每次移動兩個距離  移動X次 他也會走到那個交點處  這樣  當p2走完a個距離以后  就會與p1重合  共同在環里繞圈 知道走到交點   所以   這樣就可以求出 環的初始位置了。

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈