[Leetcode] 160. Intersection of two Linked Lists (相交鏈表) 題解紀錄

題目:

Intersection of two Linked Lists (相交鏈表)

難度:

簡單

解題思路:

這一題如果要做到空間複雜度為 O(1) 的話，需要使用到雙指針的方式來解題，主要原理就如同上圖

可以把兩條鏈表相交匯的部分，分離成第三個鏈表來看:

鏈表a 的 指針 定義為 (p_a)
鏈表b 的 指針 定義為 (p_b)
分開看的 鏈表c 定義為 (C)

這樣我們就可以得出 (p_a + p_b) == (p_b + p_a)，
那如果 p_a -> C -> p_b -> C1 走的的步數和 p_b -> C -> p_a -> C1 走的步數是一樣的話，我們就可以利用這樣的一個原理來找出兩的鏈表相交的節點C1了

1. 設立邊界條件: 邊界條件就是當 p_a == p_b 迴圈即跳出
2. 如果其中一條走到 None 就接到另一個鏈表

如何如果兩的鏈表不相交呢? 這一題也是可以處理不相交的兩個鏈表的，當兩個不相交鏈表都同時走到了 None 時，自然迴圈就跳出了，所以這個問題也會被解決

這一題的時間複雜度為 O(n)，空間複雜度為 O(1)