/**
 * @author wuze
 * @desc ...
 * @date 2021-03-21 14:33:23
 */
public class 两个链表的第一个公共节点_字节面试_剑指offer52 {


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


    public class Solution {


        /*
    方法二:双指针法(我走过你走过的路,缘分相遇)
                    (如果我走你的路走到黑，还没遇到你，就再也不相遇，返回null)
    */
        public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
            if(headA==null || headB==null){
                return null;
            }
            ListNode tmpA=headA;
            ListNode tmpB=headB;
            int flag1=0;
            int flag2=0;

            //当相遇时退出循环
            while(tmpA!=tmpB){
                /*
                //法1:简练写法
                tmpA=tmpA.next == null ? headB : tmpA.next;
                tmpB=tmpB.next == null ? headA : tmpB.next;
                */

                //法2:具体写法
                //如果tmpA走到尽头,就去走tmpB的路
                tmpA=tmpA.next;
                if(tmpA==null && flag1==0){
                    flag1=1;
                    tmpA=headB;
                }
                //如果我走你的路走到黑，还没遇到你，就再也不相遇，退出循环
                if(tmpA==null && flag1==1){
                    break;
                }

                //如果tmpB走到尽头,就去走tmpA的路
                tmpB=tmpB.next;
                if(tmpB==null && flag2==0){
                    tmpB=headA;
                }
                //同理
                if(tmpB==null && flag2==1){
                    break;
                }

                //当两者相等时,就是第一个相遇的点,因为前面tmpA和tmpB走的路是同样距离的!

            }
            return tmpA;
        }




        /*
        方法一:暴力法
        */
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if(headA==null || headB==null){
                return null;
            }
            //特殊情况:headA和headB都只有一个元素
            if(headA.next==null && headB.next==null && headA==headB){
                return headA;
            }

            //对每一个headA都遍历每一个headB
            while(true){
                //边界判断
                if(headA==null){
                    return null;
                }
                if(headA==null && headB==null){
                    return null;
                }
                if(headA.next==null && headB.next==null && headA!=headB){
                    return null;
                }
                //对每一个headA都遍历每一个headB
                ListNode tmpNode=headB;
                while(tmpNode.next!=null){
                    if(tmpNode==headA){
                        return headA;
                    }
                    tmpNode=tmpNode.next;
                }

                if(headA.next!=null){
                    //向后移动headA
                    headA=headA.next;
                }else if(headA.next==null && headA==tmpNode){
                    //headA到尾部,并且该元素等于headB尾部元素(也就是重叠)
                    return headA;
                }else if(headA.next==null && headA!=tmpNode){
                    //两个链表完全没有重叠部分,返回null
                    return null;
                }

            }
            //return null;
        }
    }

}