两条链表相交节点问题

可以分为链表是否有环来拆分问题

package dayone.tre;

public class IntersectNode {


    public static Node getIntersectNode(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        //判断链表是否有环，如果有环则返回入环节点，否则返回null
        Node loop1 = getLoopNode(head1);
        Node loop2 = getLoopNode(head2);
　　　　　
        if (loop1 == null && loop2 == null) {
            return noLoop(head1, head2);
        }

        if (loop1 != null && loop2 != null) {
            return bothLoop(head1, loop1, head2, loop2);
        }
        return null;
    }

    /***
     * 获取入环节点
     *
     * 通过快慢指针寻找入环节点（快指针一次走2步，慢指针一次走一步），如果链表有环则快慢指针一定会在最大绕环2圈内相交,相交后快指针回到初始点，
     * 随后慢指针和快指针继续运行，都每次走一步，则快慢指针相遇时就是入环节点（感兴趣的朋友可以去查一下，列一下方程）
     * @param head
     * @return
     */
    private static Node getLoopNode(Node head) {
        //如果节点小于三无法成环
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node n1 = head.next;
        Node n2 = head.next.next;
        while (n1 != n2) {
            //如果快指针出现空时还没有相遇说明每环
            if (n2.next == null || n2.next.next == null) {
                return null;
            }
            n1 = n1.next;
            n2 = n2.next.next;
        }
        n2 = head;
        while (n1 != n2) {
            n1 = n1.next;
            n2 = n2.next;
        }

        return n1;
    }

    /***
     * 两个链表都无环
     *  连个链表如果相交则后序节点必须重合（链表只有一个next指针）
     * @param head1
     * @param head2
     * @return
     */
    private static Node noLoop(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        int n = 0;
        Node cur1 = head1;
        Node cur2 = head2;
        //遍历cur1和cur2统计长度差n
        while (cur1.next != null) {
            n++;
            cur1 = cur1.next;
        }
        while (cur2.next != null) {
            n--;
            cur2 = cur2.next;
        }
        //如果两个链表最后一个节点都不相同,则两个链表必不相交（因为链表只有一个next指针，所以一旦两链表相交则后序节点应重合）
        if (cur1 != cur2) {
            return null;
        }
        //将长链表赋值给cur1
        cur1 = n > 0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2 : head1;
        //取绝对值
        n = Math.abs(n);
        //长链表先走n步
        while (n != 0) {
            n--;
            cur1 = cur1.next;
        }
        //寻找两链表相遇点
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }

        return cur1;
    }

    private static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
        Node cur1;
        //如果在入环节点前则转换为无环链表相遇问题
        if (loop1 == loop2) {
            return noLoop(head1, head2);
        } else {
            cur1 = loop1.next;
            //两个两边在环上相交，则loop2一定在head1的环上，遍历head1就能找到相交的节点，如果没有找到说明不想交
            while (cur1 != loop1) {
                if (cur1 == loop2) {
                    return loop1;
                }
                cur1 = cur1.next;
            }
            return null;
        }
    }


    class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }
}