1.11 如何判斷兩個單鏈表（無環）是否交叉

【出自WR筆試題】

難度系數：★★★★☆

被考察系數：★★★★★

題目描述：

單鏈表相交指的是兩個鏈表存在完全重合的部分，如下圖所示。

在上圖中，這兩個鏈表相交于結點5，要求判斷兩個鏈表是否相交，如果相交，找出相交處的結點。

分析與解答：

方法一：Hash法

如上圖所示，如果兩個鏈表相交，那么它們一定會有公共的結點，由于結點的地址或引用可以作為結點的唯一標識，因此，可以通過判斷兩個鏈表中的結點是否有相同的地址或引用來判斷鏈表是否相交。具體可以采用如下方法實現：首先遍歷鏈表head1，把遍歷到的所有結點的地址存放到HashSet中；接著遍歷鏈表head2，每遍歷到一個結點，就判斷這個結點的地址在HashSet中是否存在，如果存在，那么說明兩個鏈表相交并且當前遍歷到的結點就是它們的相交點，否則直到鏈表head2遍歷結束，說明這兩個單鏈表不相交。

算法性能分析：

由于這種方法需要分別遍歷兩個鏈表，因此，算法的時間復雜度為O（n1+n2）。其中，n1與n2分別為兩個鏈表的長度。此外，由于需要申請額外的存儲空間來存儲鏈表head1中結點的地址，因此，算法的空間復雜度為O（n1）。

方法二：首尾相接法

主要思路：將這兩個鏈表首尾相連（如把鏈表head1尾結點鏈接到head2的頭指針），然后檢測這個鏈表是否存在環，如果存在，則兩個鏈表相交，而環入口結點即為相交的結點，如下圖所示。具體實現方法以及算法性能分析見1.6節。

方法三：尾結點法

主要思路：如果兩個鏈表相交，那么兩個鏈表從相交點到鏈表結束都是相同的結點，必然是Y字形（如上圖所示）。所以，判斷兩個鏈表的最后一個結點是不是相同即可。即先遍歷一個鏈表，直到尾部，再遍歷另外一個鏈表，如果也可以走到同樣的結尾點，則兩個鏈表相交，這時記下兩個鏈表的長度n1、n2，再遍歷一次，長鏈表結點先出發前進|n1-n2|步，之后兩個鏈表同時前進，每次一步，相遇的第一點即為兩個鏈表相交的第一個點。實現代碼如下：

程序運行結果為

運行結果分析：

在上述代碼中，由于構造的兩個單鏈表相交于結點5，因此，輸出結果中它們的相交結點為5。

算法性能分析：

假設這兩個鏈表長度分別為n1、n2，重疊的結點的個數為L（0＜L＜min（n1,n2）），則總共對鏈表進行遍歷的次數為n1+n2+L+n1-L+n2-L=2（n1+n2）-L。因此，算法的時間復雜度為O（n1+n2）。由于這種方法只使用了常數個額外指針變量，因此，空間復雜度為O（1）。

引申：如果單鏈表有環，如何判斷兩個鏈表是否相交。

分析與解答：

1）如果一個單鏈表有環，另外一個沒有環，那么它們肯定不相交。

2）如果兩個單鏈表都有環并且相交，那么這兩個鏈表一定共享這個環。判斷兩個有環的鏈表是否相交的方法為：首先采用本章1.6節中介紹的方法找到鏈表head1中環的入口點p1，然后遍歷鏈表head2，判斷鏈表中是否包含結點p1，如果包含，則這兩個鏈表相交，否則不相交。找相交點的方法：把結點p1看作兩個鏈表的尾結點，這樣就可以把問題轉換為求兩個無環鏈表相交點的問題，可以采用本節介紹的求相交點的方法來解決這個問題。