如何判斷兩鏈表是否相交，相信很多沒有經(jīng)驗的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。

創(chuàng)新互聯(lián)是專業(yè)的麻江網(wǎng)站建設(shè)公司，麻江接單;提供成都網(wǎng)站建設(shè)、網(wǎng)站制作,網(wǎng)頁設(shè)計,網(wǎng)站設(shè)計,建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進行麻江網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團隊,希望更多企業(yè)前來合作!

給定兩單鏈表A、B，只給出兩頭指針。請問：

1、如何判斷兩單鏈表（無環(huán)）是否相交？

有兩種可取的辦法：

（1）人為構(gòu)環(huán)，將鏈表A的尾節(jié)點指向鏈表B，再判斷是否構(gòu)環(huán)成功？從鏈表B的頭指針往下遍歷，如果能夠回到B，則說明相交

（2）判斷兩鏈表最后一個節(jié)點是否相同，如果相交，則尾節(jié)點肯定是同一節(jié)點

2、如何判斷兩單鏈表（不知是否有環(huán)）相交？

先判斷是否有環(huán)，判斷是否有環(huán)可以使用追逐辦法，設(shè)置兩個指針，一個走一步，一個走兩步，如果能相遇則說明存在環(huán)

（1）兩個都沒環(huán)：回到問題1

（2）一個有環(huán)，一個沒環(huán)：不用判斷了，肯定兩鏈表不相交

（3）兩個都有環(huán)：判斷鏈表A的碰撞點是否出現(xiàn)在鏈表B的環(huán)中，如果在，則相交。（相交時，環(huán)必定是兩鏈表共有的）

3、如何尋找兩相交鏈表（不知是否有環(huán)）的第一個相交節(jié)點？

同樣，使用追逐辦法先判斷是否存在環(huán)，分情況討論

（1）無環(huán)：人為構(gòu)環(huán)，將鏈表A的尾節(jié)點指向鏈表B，則構(gòu)成一個帶環(huán)的單鏈表。這個問題就轉(zhuǎn)換成尋找?guī)Лh(huán)單鏈表的環(huán)入口節(jié)點。

    解法參考：連接點此

（2）有環(huán)：計算出兩鏈表的長度lA、lB，（環(huán)的長度和環(huán)到入口點長度之和就是鏈表長度）

計算帶環(huán)鏈表長度，可參考http://blog.csdn.net/liuxialong/archive/2011/06/20/6555850.aspx

如果lA>lB，則鏈表A指針先走lA-lB，然后鏈表B指針開始走，兩者相遇的點就是相交點

如果lB>lA，則鏈表B指針先走lB-lA，然后鏈表A指針開始走，兩者相遇的點就是相交點

鏈表有環(huán)否 也可參考此處  是否有環(huán)

看完上述內(nèi)容，你們掌握如何判斷兩鏈表是否相交的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！