兩個(gè)單鏈表只能存在Y型交叉，不會(huì)存在X型交叉。最簡(jiǎn)單的方式是直接遍歷到兩個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)，判斷它們是否相同。但這樣做有兩個(gè)問題，一是時(shí)間較長(zhǎng)（尤其是鏈表很長(zhǎng)的時(shí)候），其次是無法找到第一個(gè)交叉的點(diǎn)。應(yīng)該如何改進(jìn)呢？

判斷最后一個(gè)節(jié)點(diǎn)是否相同的辦法并不慢，如果兩個(gè)鏈表長(zhǎng)度m,n 那么復(fù)雜度O(m+n)，這是最優(yōu)的復(fù)雜度

第二個(gè)問題，如何尋找交叉節(jié)點(diǎn):

指針p、q分別遍歷鏈表a、b，假設(shè)q先到達(dá)NULL（即 假設(shè)a 比 b 長(zhǎng)），此時(shí)從a的頭發(fā)出一個(gè)指針t,當(dāng)p到達(dá)NULL時(shí),從b的頭發(fā)出s,當(dāng)s==t的時(shí)候即交點(diǎn).