算法打卡Day10_leetcode _160.相交链表

 //方法3： 采用了双指针： 时间复杂度O(m+n),空间复杂度O(1)
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA ==null ||  headB ==null){
            return null;
        }
        ListNode aPro =headA;
        ListNode bPro =headB;
        while (aPro!= bPro){
            //a指针不能空，则移向下一个节点；为空，则移动到b头节点继续移动
            aPro = aPro==null? headB:aPro.next;
            //b指针不能空，则移向下一个节点；为空，则移动到a头节点继续移动
            bPro = bPro==null? headA:bPro.next;
        }
        //当指针pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。
        return aPro;
    }

  //方法4：统计2个链表各自长度，然后根据长度，计算差值d。
    //1.把较长的链表移动d步。此时2个链表相同长度
    //2.移动2个链表，如果走到相同的节点，说明存在相交
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA ==null ||  headB ==null){
            return null;
        }
        ListNode aPro =headA;
        ListNode bPro =headB;
        int lenA=0,lenB=0,diff=0;
        while (aPro!=null){
            lenA++;
            aPro=aPro.next;
        }
        while (bPro!=null){
            lenB++;
            bPro =bPro.next;
        }
        if (lenA>lenB){
            //a的链表长度大于b,同时定义aPro为长链表，b为短链表
            diff = lenA-lenB;
            aPro= headA;
            bPro =headB;
        }else {
            diff =lenB-lenA;
            aPro= headB;
            bPro =headA;
        }
        for (int i = 0; i < diff; i++) {
            //长链表先移动diff步
            headA =headA.next;
        }
        while (headA!= null && headB!=null){
             if (headA == headB){
                 return headA;
             }
             headA =headA.next;
             headB =headB.next;
        }
        return null;
    }