題目

有兩個單向鏈表, 兩個鏈表情況如下:

1. 兩個鏈表可能相交, 也可能不相交
2. 可能有環, 也可能無環

現給定兩個鏈表的頭節點, 若相交, 返回相交的第一個節點, 若不相交, 返回null

要求: 鏈表一長度N, 鏈表二長度M, 時間複雜度O(N+M)

思路分析

要想解決兩個鏈表的相交問題, 可以分不同的情況來討論:

1.若兩鏈表均無環, 那麼就只能是不相交或兩鏈表匯於一點

這種情況, 可以遍歷兩個鏈表, 判斷末尾節點是否為同一節點, 若不是則不相交, 若是, 鏈表一長度為40, 鏈表二長度為50, 令鏈表二先走10步, 之後兩鏈表同步走, 相遇的點就是相交的第一個節點, 這應該不難理解, 就相當於將上圖右側的折以下.

2.若一個鏈表有環, 另一個無環, 則必不會相交. 因為無環鏈表若與有環鏈表相交, 則指針向後會隨有環鏈表而有環, 破壞無環鏈表, 所以這種情況必不相交.

3.若兩鏈表都有環, 則有三種情況, (1)不相交 (2)在環上相交 (3)在入環前相交 如圖:

這時進行判斷, 若兩鏈表的入環節點相同, 則相交, 為圖中第二中情況, 這時求相交節點, 不就可以將環去掉, 看成兩個無環鏈表麼? 這就回到了情況1, 完美.

若兩鏈表入環節點不相同, 圖中第一和第三種情況, 那麼如何區分這兩種結構呢? 令鏈表一的入環節點向後走, 若走了一圈都沒遇到鏈表二的入環節點, 則為圖中第一種情況, 若遇到了, 則為圖中第三種情況, 此時返回任意一個即可.

實現

好, 基本思路有了, 下面首先判斷鏈表是否有環, 判斷的方法有很多, 如:

1. 使用兩個指針, 指針A從頭向後依次訪問, 每到一個節點, 指針B從頭查找該節點, 若兩次步數不相同, 則存在環
2. 使用快慢指針, 指針A每次向後走兩步, 指針B每次向後走一步, 若存在 p == q的情況, 則存在環, 此時令快指針A回到頭節點, 兩指針同時向後走, 每次走一步, 當第一次相遇時, 為第一個入環節點
3. 遍歷鏈表, 每次將對象加到HashSet中, 若當某次加的時候, 發現已經加過該對象了, 則存在環(此方法對基本類型無效)

下面使用第二種方法來實現, 簡單的Java代碼實現:

鏈表是否有環完事了, 下面就是分情況來實現查找第一個相交節點的方法:

1.若兩鏈表無環, 根據上面的思路實現代碼如下:

2, 若一個鏈表有環,一個鏈表無環, 直接返回null即可

3.若兩鏈表均有環, 根據上面思路實現代碼如下:

完成, 下面用一個方法將上面的方法串起來就可以了, 主方法如下:

結束!!!

閱讀更多 牛牛的編程之路 的文章

關鍵字: 鏈表 相交 算法設計