從LeetCode學演算法 - 44 Linked List (5)

0160. Intersection of Two Linked Lists (Easy)

Question

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

For example, the following two linked lists:

begin to intersect at node c1.

Example 1

1
2
3
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2

1
2
3
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3

1
2
3
4
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

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.

分析/解題

有兩個單向連結串列，試找出其交會開始的節點。
如果它們彼此之間沒有相交，則回傳null。
(注意中提到最好時間使用O(n)且空間僅使用O(1)。)

這題其實相當簡單，但要特別留意一點：
就算兩個節點的值相等，也並不代表它們是同一個節點。
從Example 1中就可以看到這個例子，
節點值都是1，但並非同節點，這部分要特別留意。
不過我們並未特別針對ListNode去實作相等的function的狀況下，
直接用**==** 判斷即可。

那麼，怎麼來找共同的交會節點呢？
我們可以先假設它們有一個交會點，
那麼list A跟list B在這個交會點(含)以後的節點數會相等。
(因為重合了XD)

所以比如說A總長度是9，B總長度是6，
我們可以先讓A從開頭走3步 ，(這樣才能對齊 )
接著兩邊開始依序走訪比對走到的節點是否交會，
若交會則回傳；若走到底還沒有看到相同的節點，
則回傳null(或None)。

所以大體上的操作如下：

設定iteA/iteB作為走訪list A/list B用的節點
先各自走訪過一輪來取得A和B分別的長度
長度相減，讓比較長的list的起始節點先多走相差的節點數
同時開始第二次的走訪，一邊比對節點是否交會，
是則回傳該節點，不是則走到至少一邊走完為止
若4走完尚未回傳則回傳null(表示沒有交會)

寫成程式碼如下。

Java

Python的部分可以寫得稍微簡潔一點，
留意用來遞進用的迴圈這裡的for會使用單底線，
因為我們只想要使用重複diff或-diff次的功能，
並不在意迴圈執行到第幾次。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N), O(1)，我們共遍歷了最多兩次的list，
且只有額外使用到幾個輔助用的節點和變數。)

相似及延伸

1.0599. Minimum Index Sum of Two Lists

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~