判斷兩個連結串列是否相交，如何判斷單連結串列是否相交併找出第一交點

1樓：匿名使用者

址值是否已經存在於上面建立的hash表中。

如何判斷單連結串列是否相交併找出第一交點

2樓：世紀網路

1.判斷連結串列否是相交？

解法一：雜湊表法，維護乙個雜湊表，分別遍歷兩個連結串列。將它們中的元素存入雜湊表中，如果元素有重複那麼兩個連結串列就相交。

解法二：還有一種比較有想象力的解法，先遍歷第乙個連結串列到他的尾部，然後將尾部的next指標指向第二個連結串列(尾部指標的next本來指向的是null)。這樣兩個連結串列就合成了乙個連結串列，判斷原來的兩個連結串列是否相交也就轉變成了判斷新的連結串列是否有環的問題了：

即判斷單連結串列是否有環？

這樣進行轉換後就可以從連結串列頭部進行判斷了，其實並不用。通過簡單的瞭解我們就很容易知道，如果新連結串列是有環的，那麼原來第二個連結串列的頭部一定在環上。因此我們就可以從第二個連結串列的頭部進行遍歷的，從而減少了時間複雜度(減少的時間複雜度是第乙個連結串列的長度)。

解法三：仔細研究兩個連結串列，如果他們相交的話，那麼他們最後的乙個節點一定是相同的，否則是不相交的。因此判斷兩個連結串列是否相交就很簡單了，分別遍歷到兩個連結串列的尾部，然後判斷他們是否相同，如果相同，則相交；否則不相交。

2.如果相交求出交點？

解法一：如果可以分配較多的記憶體，先遍歷連結串列a，遍歷連結串列a的時候將node加入到乙個hash表或者二叉樹中。之後遍歷連結串列b的node時，檢查該node是否存在在資料結構中對應的位置就可以了。

可能會比原始方法快一些（如果交點在連結串列中靠後的位置，這個代價可能就比較大了，因為要維護多餘的資料結構，因此這種情況下實踐中效率很可能比原始方法慢），不過會使用較多的記憶體空間。

解法二：遍歷兩個表分別知道兩個表的長度a, b。然後讓長表先走|a-b|步後，短表再開始走，直到相同，則相同的的第乙個節點為交點。

如何判斷兩個單向連結串列是否有相交，並找出交點

3樓：薔觀九

連結串列1,2均沒有環。

把連結串列1首尾相連，判斷連結串列2是否有環，若有環，則相交。

基本思路2：

遍遍歷連結串列1,2,若尾指標相等，則相交。

連結串列1和連結串列2的長度想減求絕對值，較長的連結串列先移動差值個位置，然後兩個連結串列同時移動，相等的地方即為交點。演算法也不給出了。