yoruru的努力日記

160. Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

• intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
• listA - The first linked list.
• listB - The second linked list.
• skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
• skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

 

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
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,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
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 [1,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:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
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.

 

Constraints:

• The number of nodes of listA is in the m.
• The number of nodes of listB is in the n.
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA < m
• 0 <= skipB < n
• intersectVal is 0 if listA and listB do not intersect.
• intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

 

Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?

---

SOL：

這一題我覺得光是讀懂題目就是一個挑戰了。

主要是要找兩個 linked list 有沒有相交的部分，因此就算值是一樣的，但在記憶體中指向不同的位置，依然不是我們要的。

暴力法是將一個 linked list 全部拜訪過，記下每個node來後，再去比對另一個 linked list 是否相同。

暴力法參考：Leetcode — 160. Intersection of Two Linked Lists (中文)

我的程式碼也是參考這一篇文，但在寫的時候一值很好奇程式是怎麼比對的，把 nodeSet 印出來之後就理解了。

以 headA = [4,1,8,4,5] 來說，各別看一下 nodeSet 會長怎樣。

nodeSet 加入第一個元素：

set([ListNode{val: 4, next: ListNode{val: 1, next: ListNode{val: 8, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}}])

nodeSet 加入第一,二個元素：

set([ListNode{val: 4, next: ListNode{val: 1, next: ListNode{val: 8, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}}, ListNode{val: 1, next: ListNode{val: 8, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}])

nodeSet 加入第一~三個元素：
set([ListNode{val: 4, next: ListNode{val: 1, next: ListNode{val: 8, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}}, ListNode{val: 1, next: ListNode{val: 8, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}, ListNode{val: 8, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}])

....

以此類推，所以當我們在檢查 headB 有沒有在 nodeSet 中，才能抓出 val 一樣，next 也一模一樣的 ListNode。

Python Set 的用法參考：[Python] 學習使用集合 (Set)

How to check if a set contains an element in Python?

但這樣的暴力法當然不能滿足面試所需，接下來學習一下空間複雜度降到 O(1) 的做法。

參考影片：LeetCode in Python 160. Intersection of Two Linked List - Michelle小梦想家

做法的核心是，兩個 linked list 同時都走一步，當走到尾的時候跳到對方的 head 繼續走。

原理是因為當我們假設A、B這兩個 list 有相同的 common list。

A = A' + common

B = B' + common

我們的所求是能夠排除掉前面讓兩個 list 不同的 A' 跟 B'，找出 common list。

當自己的 list 走完就走對方的時候，就會變成兩者都是在走 A+B，長度會變成一樣。

對A來說：A+B = (A' + common) + B' + common

對B來說：B+A = (B' + common) + A' + common

因此走到相同 common 的第一個元素，我們就可以找到 common list。

即便A、B 沒有 common list，他們一樣走完 A+B 就會走到尾，變成 null == null 回傳。

順帶一提，python 沒有 null，只有 None。