# Description

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

• 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.

# Example

Example 1:

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

Output: c1
Explanation ：begin to intersect at node c1.

Example 2:

Input:
Intersected at 6
1->2->3->4->5->6->7->8->9->10->11->12->13->null
6->7->8->9->10->11->12->13->null
Output: Intersected at 6
Explanation：begin to intersect at node 6.

Challenge

Your code should preferably run in O(n) time and use only O(1) memory.

# Code

找交接點：
兩個 List 加起來的長度是一樣的都是 A＋B
當 A 走到為空時，接上 B (原本題目給的 headB)
B 到空，接上 A

e.g
A: 1-2-3-7-8-9-4-7-8-9
B: 4-7-8-9-1-2-3-7-8-9

最後交接點會是一樣的位置

/**

 * Definition for ListNode

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

     // 時間複雜度是 ON，空間 O1

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

       // 讓 p1 遍歷完 headA 就開始遍歷 headB, p2 遍歷完 headB 就開始遍歷 headA, 讓它們邏輯上接在一起

       //p1 指向 headA, p2 指向 headB

       ListNode p1 = headA, p2 = headB;

       while (p1 != p2){

           //p1 走一步， 如果走到 A 鏈表末尾，轉到 B 鏈錶

           if (p1 == null){

               p1 = headB;

           } else {

               p1 = p1.next;

           }

            //p2 走一步， 如果走到 B 鏈表末尾，轉到 A 鏈錶

           if(p2 == null){

               p2 = headA;

           } else {

               p2 = p2.next;

           }

       }

       return p1;

    }

}