public class SO52_getIntersectionNode {
    class ListNode {
        int val;
        ListNode next;
        public ListNode(int x){
            val =x;
            next = null;
        }
    }

    public static void main(String[] args) {

    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        int countA = 0;
        int countB = 0;
        ListNode pNodeA = headA, pNodeB = headB;
        while (pNodeA != null) {
            countA++;
            pNodeA = pNodeA.next;
        }
        while (pNodeB != null) {
            countB++;
            pNodeB = pNodeB.next;
        }
        pNodeA = headA;
        pNodeB = headB;
        int dis = Math.abs(countA-countB);
        if (countA > countB) {
            while (dis != 0 ) {
                pNodeA = pNodeA.next;
                dis--;
            }
        } else if (countA < countB) {
            while (dis != 0) {
                pNodeB = pNodeB.next;
                dis--;
            }
        }
        while(pNodeA != null || pNodeB != null) {
            if (pNodeA != pNodeB) {
                pNodeA = pNodeA.next;
                pNodeB = pNodeB.next;
            } else {
                break;
            }
        }
        return pNodeA;
    }

    // 设交集链表长c,链表1除交集的长度为a，链表2除交集的长度为b，有
    //a + c + b = b + c + a
    //若无交集，则a + b = b + a
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {

        ListNode h1 = headA, h2 = headB;
        while (h1 != h2) {

            h1 = h1 == null ? headB : h1.next;
            h2 = h2 == null ? headA : h2.next;
        }

        return h1;
    }
}