链表-已知两个有环或无环的单链表，求第一个交点

* 给定两个可能有环也可能无环的单链表，头节点head1和head2。
* 请实现一个函数，如果两个链表相交，请返回相交的 第一个节点。如果不相交，返回null。
* 【要求】如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度 请达到O(1)。
* https://www.bilibili.com/video/BV13g41157hK?p=6&spm_id_from=0.0.header_right.history_list.click

---

可能一： 无环+无环

可能二： 有环+有环

可能三： 有环+无环 ： 因为是单链表， 只能有一个next，所以不可能

---

step 1. 判断链表是否有环，有则返回入环的节点，无则返回空

 public static ListNode getLoop(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }

        ListNode fast = head.next.next;
        ListNode slow = head.next;

        while (fast != slow) {
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        //快慢指针相遇后， 其中一个从头开始走， 每次一步， 两个节点再次相遇时则为入环点
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;

        }
        return slow;

    }

step 2. 无环+无环：  找到两个无环链表的交点

public static ListNode  noloop(ListNode head1, ListNode head2){
        int lencha = 0; //链表1和链表2的长度差

        //循环链表1
        ListNode start1 = head1;
        while (start1.next!=null){
            lencha ++;
            start1 = start1.next;
        }


        //循环链表2
        ListNode start2 = head2;
        while (start2.next!=null){
            lencha --;
            start2 = start2.next;
        }

        if (start1!=start2){
            return null;
        }

        //currA 代表长的链表， currB指向短的链表
        ListNode currA ;
        ListNode currB ;
        currA = lencha >0 ? head1 : head2;
        currB = currA==head1? head2: head1;
        lencha = Math.abs(lencha);
        //因为是同一个尾节点，所以长的 先走 两个链表长度差 步
        while (lencha>0){
            lencha--;
            currA = currA.next;
        }
        //A和B一起往后走，直到遇到一个相等的
        while (currA!=currB){
            currA = currA.next;
            currB = currB.next;
        }
        return currA;


    }

step 3. 有环+有环：  找到两个有环链表的交点

public static ListNode getIntersection(ListNode head1, ListNode in1, ListNode head2, ListNode in2){

        if (in1 == in2){
            // （情况1）入环点相同,则同两无环链表取交点
            ListNode curr1 = head1;
            ListNode curr2 = head2;
            int lenn = 0;
            while (curr1.next != in1){
                lenn ++;
                curr1 = curr1.next;
            }
            while (curr2.next != in2){
                lenn --;
                curr2 = curr2.next;
            }
            curr1 = lenn > 0 ? head1 : head1;
            curr2 = curr1 == head1 ? head2 : head1;
            lenn = Math.abs(lenn);
            while (lenn!=0){
                curr1 = curr1.next;
                lenn--;
            }
            while (curr1!=curr2){
                curr1 = curr1.next;
                curr2 = curr2.next;
            }
            return curr1;



        }else {
            //（情况2、情况3）入环点不同， 则判断往后走是否可相交
            ListNode curr = in1.next;
            while (curr != in1){

                if (curr == in2){
                    return in2;
                }
                curr = curr.next;
            }
            return null;

        }

    }