如何高效地判斷兩個單鏈表是否有交叉？

01-05

兩個單鏈表只能存在Y型交叉，不會存在X型交叉。最簡單的方式是直接遍歷到兩個鏈表的最後一個節點，判斷它們是否相同。但這樣做有兩個問題，一是時間較長（尤其是鏈表很長的時候），其次是無法找到第一個交叉的點。應該如何改進呢？

我想說, 對於僅判斷相交不相交的話：判斷最後一個節點是否相同的辦法並不慢，如果兩個鏈表長度m,n 那麼複雜度O(m+n)，這是最優的複雜度

第二個問題，如何尋找交叉節點:

指針p、q分別遍歷鏈表a、b，假設q先到達NULL（即假設a 比 b 長），此時從a的頭髮出一個指針t,當p到達NULL時,從b的頭髮出s,當s==t的時候即交點.

如果不明白請看:https://github.com/hit9/oldblog/blob/gh-pages/blog-src/blog/C/posts/25.mkd#9%E6%89%BE%E4%B8%A4%E4%B8%AA%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4%E7%9A%84%E4%BA%A4%E7%82%B9

遍歷兩個表分別知道兩個表的長度a, b。然後讓長表先走|a-b|步後，短表再開始走，直到相同。時間複雜度為o(m+n)

1.如果可以分配較多的內存，先遍歷鏈表A，遍歷鏈表A的時候將node加入到一個hash表或者二叉樹中，隨便你了，看你有多少內存和問題特點了。之後遍歷鏈表B的node時，檢查該node是否存在在數據結構中對應的位置就可以了。可能會比原始方法快一些（如果交點在鏈表中靠後的位置，這個代價可能就比較大了，因為要維護多餘的數據結構，因此這種情況下實踐中效率很可能比原始方法慢），不過會使用較多的內存空間。

2.如果內存很緊張的話，我短時間內想到的方法和你差不多，只是在遍歷完知道2個鏈表長度之後，交點位置a必定在較長鏈表A中「較長的鏈表A的長度」減去「2個鏈表之差的絕對值」或之後的位置，那麼只需要在較長的鏈表A遍歷到位置a的時候同時開始遍歷鏈表B，然後檢查每次遍歷的2個node是否相等就可以了。這個方法實質上沒有比你的方法快，但是解決了第二個問題（即第一個交叉點的問題）。

當然如果你已知2個鏈表的長度信息。整個問題的解決就會相當的輕鬆了。

那就用hash唄，時間複雜度o(max(length(a1),length(a2)))