如何判斷兩個鏈表是否相交，假設(shè)兩個鏈表都沒有環(huán)？

如何判斷兩個鏈表是否相交，假設(shè)兩個鏈表都沒有環(huán)？

首先，很多同學會存在一個誤區(qū)，認為兩個鏈表相交應該這樣的。

如果把它用結(jié)點的形式來表示就這樣的。

很顯然，相交的這個結(jié)點的next指針既指向了這個這個結(jié)點，又指向了這個結(jié)點，明顯不科學。

真正相交的鏈表，應該是這樣的。

如果兩個鏈表相交，那么一定有重合的結(jié)點，所以可以逐個判斷第一個鏈表里面的結(jié)點是否在第二個鏈表中，這種辦法可行，就是效率太低，放在筆試題中往往時間復雜度滿足不了。

我們稍微分析一下就會發(fā)現(xiàn)，相交的兩個鏈表，他們的最后一個結(jié)點一定是重合的。

所以只要讓第一個鏈表的指針指向最后一個結(jié)點，第二個鏈表的指針也指向最后一個結(jié)點，判斷這兩個結(jié)點是否相同，就能解決問題。

這個時候，往往面試官會接著問，如何找出相交的那個結(jié)點。

剛才的方法只適用于判斷是否相交，如果想找出相交的結(jié)點，好像不太容易。

我們得換個方法，既能判斷是否相交，又能找出相交的那個結(jié)點。

如果兩個鏈表的長度一樣，只要同時移動指針，最先相等的那個結(jié)點一定就是相交的結(jié)點。

所以可以先計算兩個鏈表的長度差，然后先移動一個指針，保證長度一樣后，再同時向后走。代碼也沒什么難度，直接附上。

審核編輯：劉清