?？途W(wǎng)高頻算法題系列-BM10-兩個鏈表的第一個公共結(jié)點(diǎn)

題目描述

輸入兩個無環(huán)的單向鏈表，找出它們的第一個公共結(jié)點(diǎn)，如果沒有公共節(jié)點(diǎn)則返回空。（注意因?yàn)閭魅霐?shù)據(jù)是鏈表，所以錯誤測試數(shù)據(jù)的提示是用其他方式顯示的，保證傳入數(shù)據(jù)是正確的）

原題目見：BM10 兩個鏈表的第一個公共結(jié)點(diǎn)

解法一：雙重循環(huán)

使用雙重循環(huán)遍歷2個鏈表，簡單粗暴，不過效率稍低。

解法二：雙指針法

使用2個指針l1和l2分別從鏈表一和鏈表二的頭結(jié)點(diǎn)遍歷，遍歷到尾部后，再分別從鏈表二和鏈表一遍歷，如果兩個鏈表有公共交點(diǎn)，則l1和l2一定會在交點(diǎn)處相遇，否則，l1和l2分別遍歷完兩個鏈表后都是null，沒有公共結(jié)點(diǎn)。

代碼

1.01^{365} ≈ 37.7834343329 ??

0.99^{365} ≈ 0.02551796445 ??

相信堅持的力量！