[LeetCode] 160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

<Solution>

這題是要找兩個 linked list 交集開始的那個 node，如果沒有交集，則回傳 NULL

因為有要求 O(1) memory，一樣不能使用 hash map

先看第一種解法，想法如下

• 先從 headA 開始，找到 headA 這條 linked list 的最後一個 node，並將它指向 headB

• 在從 headB 出發，看看是否有形成一個迴圈。如果有，就代表兩條 linked list 是有交集的；如果沒有，就回傳 NULL

• 因為有迴圈了，題目其實就變成找到迴圈的起始點，這時候就可以使用 Floyd's Circle Detection Algorithm 來找就可以了。回傳答案前記得要把迴圈給拿掉

code 如下

第二種解法十分巧妙且精簡，主要想法是利用走的步數來判斷

用題目來舉例子

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

• 當從 a1 和 b1 各自出發，相重疊的部分走的步數一定一樣，也就是 c1 到 c3  這三步

• 從 a1 走到 c3，共走了 4 步，從 b1 走到 c3 共走了 5 步。這時候， a1 出發的 node 改走到 b1，b1 出發的 node 改走到 a1，這時候，會保證兩者一定在 c1 時相遇，因為都共走了 8 步 (a1-> a2->c1->c2->c3->b1->b2->b3->c1，以及 b1->b2->b3->c1->c2->c3->a1->a2->c1)

• 如果兩者沒有交集，那最後會在都等於 NULL 時相遇(把 NULL 當作一個假想交集點)

code 如下(參考資料)