列表 環(huán) 判定 初始位置

判定的方法比較簡(jiǎn)單 有兩種方法  

第1種是使用哈希表來(lái)存貯每個(gè)節(jié)點(diǎn) 這樣的話 當(dāng)hashset[ ] 中出現(xiàn)兩個(gè)相同的節(jié)點(diǎn)時(shí)就能夠判斷出來(lái)這是1樣的了  然后他所在的那個(gè)位置就是環(huán)第1次出現(xiàn)的位置上

第2種方法是用兩個(gè)快慢指針來(lái)做  

設(shè)定兩個(gè)指針?lè)謩e為p1  p2   ，  p1的移動(dòng)速度為每次移動(dòng)1個(gè)距離   ，而p2的移動(dòng)速度為每次移動(dòng)兩個(gè)距離  ，這樣 ，直到快指針到達(dá)鏈表的結(jié)尾位置 

如果如果兩個(gè)指針相遇的話  ，那就說(shuō)明這個(gè)鏈表中存在環(huán)   ，沒(méi)有相遇的話就沒(méi)有存在環(huán)

可以想象  ，直到兩個(gè)指針相遇，慢指針在環(huán)內(nèi)的移動(dòng)距離是不會(huì)超過(guò)環(huán)的長(zhǎng)度 ，那極限來(lái)講 如果鏈表是首尾相連的  那末 慢指針的移動(dòng)距離正好為連表的長(zhǎng)度  ，如果是1個(gè)小環(huán)的話，  那末 快指針也能夠在慢指針沒(méi)有走滿半個(gè)圓環(huán)的時(shí)間內(nèi)追上慢指針。

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

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)