刷題日記（7）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:

begin to intersect at node c1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,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,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.

Example 2:

Input: intersectVal = 2, listA = [1,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 [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: 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.
• Each value on each linked list is in the range [1, 10^9].
• Your code should preferably run in O(n) time and use only O(1) memory.

解題思路(如果兩者有交集的話)

1. 先找到headA的尾巴，然後接到headB上變成循環list
2. 從headA和他的next放置兩個pointer slow和fast
3. 利用（while迴圈）slow（走一步）和fast（走兩步）找到兩者到中間交集距離一樣的位置（修正位置）
4. 最後再跑一次while迴圈的slow和fast各走一步確定交集node

(main function)

1. 設定一個base case 如果headA或headB是null的話則返回null(沒有共同交集點)
2. 新增一個node pointer給headA，然後while迴圈一路到最後當node.next=null時，代表找到結尾了
3. 接著把尾巴node.next指向headB，使其變成一個循環list
4. 然後把headA丟到helper function(listCycleII)

(listCycleII)
5. 設一個pointer slow 給headA的head, 然後再設一個pointer fast給headA的next

6. while迴圈開始比較當slow不等於fast的時候，slow往前走一步，fast往前走兩步

7.並且當fast或fast.next等於null時，return null(代表了兩個list沒有交集，所以才會走到null)

8. 當兩者slow和fast相遇時就結束迴圈

9. 接著把slow這個pointer挪回一開始傳進來的headA

10.接著fast先往前走一步

11.開始while迴圈當slow和fast不相等時，slow和fast各往前走一步

12. 最後return slow回main function

(main function)

13.拿一個pointer result去接住helper function傳回來的結果

14.因為命題說不能modify list, 所以要記得把之前接上的循環list給斷開（node.next=null）

15.最後return result

以這個為範例

找到headA的尾巴

把尾巴接到headB上

從head和他的next設置pointer slow和fast

開始slow走一步，fast走兩步

，最後兩個相遇的位置會是剛好listA和listB差一步的地方

這時fast再往前走一步，兩者到中間的交集就一樣的步數了，然後再把slow移回headA 所在位置

同樣的起點開始一步一步走

直到相遇找到交集回傳