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

首先，很多同學(xué)會(huì)存在一個(gè)誤區(qū)，認(rèn)為兩個(gè)鏈表相交應(yīng)該這樣的。

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

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

真正相交的鏈表，應(yīng)該是這樣的。

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

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

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

這個(gè)時(shí)候，往往面試官會(huì)接著問，如何找出相交的那個(gè)結(jié)點(diǎn)。

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

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

如果兩個(gè)鏈表的長度一樣，只要同時(shí)移動(dòng)指針，最先相等的那個(gè)結(jié)點(diǎn)一定就是相交的結(jié)點(diǎn)。

所以可以先計(jì)算兩個(gè)鏈表的長度差，然后先移動(dòng)一個(gè)指針，保證長度一樣后，再同時(shí)向后走。代碼也沒什么難度，直接附上。

審核編輯：劉清