溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
如何判斷兩鏈表是否相交，相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。
給定兩單鏈表A、B，只給出兩頭指針。請問：
1、如何判斷兩單鏈表（無環）是否相交？
有兩種可取的辦法：
（1）人為構環，將鏈表A的尾節點指向鏈表B，再判斷是否構環成功？從鏈表B的頭指針往下遍歷，如果能夠回到B，則說明相交
（2）判斷兩鏈表最后一個節點是否相同，如果相交，則尾節點肯定是同一節點
2、如何判斷兩單鏈表（不知是否有環）相交？
先判斷是否有環，判斷是否有環可以使用追逐辦法，設置兩個指針，一個走一步，一個走兩步，如果能相遇則說明存在環
（1）兩個都沒環：回到問題1
（2）一個有環，一個沒環：不用判斷了，肯定兩鏈表不相交
（3）兩個都有環：判斷鏈表A的碰撞點是否出現在鏈表B的環中，如果在，則相交。（相交時，環必定是兩鏈表共有的）
3、如何尋找兩相交鏈表（不知是否有環）的第一個相交節點？
同樣，使用追逐辦法先判斷是否存在環，分情況討論
（1）無環：人為構環，將鏈表A的尾節點指向鏈表B，則構成一個帶環的單鏈表。這個問題就轉換成尋找帶環單鏈表的環入口節點。
解法參考：連接點此
（2）有環：計算出兩鏈表的長度lA、lB，（環的長度和環到入口點長度之和就是鏈表長度）
計算帶環鏈表長度，可參考http://blog.csdn.net/liuxialong/archive/2011/06/20/6555850.aspx
如果lA>lB，則鏈表A指針先走lA-lB，然后鏈表B指針開始走，兩者相遇的點就是相交點
如果lB>lA，則鏈表B指針先走lB-lA，然后鏈表A指針開始走，兩者相遇的點就是相交點
鏈表有環否 也可參考此處 是否有環
看完上述內容，你們掌握如何判斷兩鏈表是否相交的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
