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.

Solution1：Two pass

思路：先count 各自length，根据len关系move至同步，在依次比较判断。
Time Complexity: O(N) Space Complexity: O(1)

Solution2：One pass

思路：a/b到尾时分别重走对方的list，这样下一次回同时到达交点处，因为都走过了相同的长度：a和b独自非交长度的总和。如果没有交点，到达null返回null
Time Complexity: O(N) Space Complexity: O(1)

Solution1 Code：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = length(headA), lenB = length(headB);
        
        // move headA and headB to the same start point
        while (lenA > lenB) {
            headA = headA.next;
            lenA--;
        }
        while (lenA < lenB) {
            headB = headB.next;
            lenB--;
        }
        
        // find the intersection until end
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }

    private int length(ListNode node) {
        int length = 0;
        while (node != null) {
            node = node.next;
            length++;
        }
        return length;
    }
}

Solution2 Code：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //boundary check
        if(headA == null || headB == null) return null;

        ListNode a = headA;
        ListNode b = headB;

        // if a & b have different len, then we will stop the loop after second iteration
        while( a != b){
            // for the end of first iteration, we just reset the pointer to the head of another linkedlist
            a = a == null? headB : a.next;
            b = b == null? headA : b.next;    
        }
        return a;
    }
}

Solution2 Round1 Code：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        
        ListNode cur_a = headA;
        ListNode cur_b = headB;

        while(cur_a != cur_b) {
            
            if(cur_a == null) {
                cur_a = headB;
            } 
            else {
                cur_a = cur_a.next;
            }
            
            if(cur_b == null) {
                cur_b = headA;
            } 
            else {
                cur_b = cur_b.next;
            }
            
        }

        return cur_a;
    }
}