[数据结构与算法]第二章 链表问题（两个单链表相交的一系列问题）

【题目】

? ? ? ?单链表可能有环，可能无环头节点 head1 和 head2， 这两个链表可能相交,也可能不相交。请实现一个函数， 如果两个链表相交， 请返回相交的第一个节点； 如果不相交， 返回 null 即可。
?如果链表1的长度为N，链表2的长度为M，时间复杂度请达到O(N + M)，额外的空间复杂度请达到O(1)。

【解答】

?????????三个子问题，具体如下。
? ????????问题一：如何判断一个链表是否有环，如果有，返回第一个进入环的节点，没有则返回null。
? ????????问题二：如何判断两个无环链表是否相交，相交则返回第一个相交节点，不相交则返回null。
? ????????问题三：如何判断两个有环链表是否相交，相交则返回第一个相交节点，不相交返回null。
? ????????注意：一个链表有环，一个无环，二者不可相交，直接返回null。

????????

package base;

public class P69_NodeCross {

    /**
     * 获取入环节点
     * @param node1 节点1
     * @param node2 节点2
     * @return
     */
    public static Node getCrossNode(Node node1, Node node2) {
        if (null == node1 || null == node2) {
            return null;
        }
        // 查看是否有环
        Node loop1 = isCircle(node1);
        Node loop2 = isCircle(node2);
        // 1、无环相交
        if (null == loop1 && null == loop2) {
            return noCircleCross(node1, node2);
        }
        // 2、有环相交
        if (loop1 != null && loop2 != null) {
            return nodeCross(node1, loop1, node2, loop2);
        }
        return null;
    }


    // 设置一个快慢指针，如果链表有环，那么快指针和慢指针一定会在环中的某个位置相遇，当快指针和慢指针相遇时，快指针重新回到head位置,
    // 改为每次移动一步，慢指针依然一次移动一步；快慢指针再次相遇的位置，就是入环节点
    public static Node isCircle(Node node) {
        if (node.next == null || node.next.next == null) {
            return null;
        }
        Node slow = node.next;
        Node fast = node.next.next;
        while (slow != fast) {
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = node;
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    /**
     * 无环相交
     * 如果两个无环节点相交，那么从相交节点开始，一直到两个链表终止的这一段，是连个链表共享的
     * @param head1
     * @param head2
     * @return
     */
    public static Node noCircleCross(Node head1, Node head2) {
        int n = 0;
        Node node1 = head1;
        while (node1 != null) {
            node1 = node1.next;
            n++;
        }
        Node node2 = head2;
        while (node2 != null) {
            node2 = node2.next;
            n--;
        }
        // node1 为长度较长节点
        node1 = n > 0 ? head1 : head2;
        node2 = node1 == head1 ? head2 : head1;
        n = Math.abs(n);
        // node1 先走n步，然后两个链表一起走，两个链表第一次走到一起的节点就是第一个相交节点
        while (n > 0) {
            n--;
            node1 = node1.next;
        }
        while (node1 != null && node2 != null) {
            if (node1 == node2) {
                return node1;
            }
            node1 = node1.next;
            node2 = node2.next;
        }
        return null;
    }

    /**
     * 有环相交
     * @param head1 节点1
     * @param loop1 入环节点1
     * @param head2 节点2
     * @param loop2 入环节点2
     * @return
     */
    public static Node nodeCross(Node head1, Node loop1, Node head2, Node loop2) {
        // 如果入环节点相等
        if (loop1 == loop2) {
            int n = 0;
            Node node1 = head1;
            while (node1 != loop1) {
                node1 = node1.next;
                n++;
            }
            Node node2 = head2;
            while (node2 != loop2) {
                node2 = node2.next;
                n--;
            }
            node1 = n > 0 ? head1 : head2;
            node2 = node1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while (n > 0) {
                n--;
                node1 = node1.next;
            }
            while (node1 != node2) {
                node1 = node1.next;
                node2 = node2.next;
            }
            return node1;
        } else {
            Node temp1 = loop1.next;
            while (temp1 != loop1) {
                if (temp1 == loop2) {
                    return loop2;
                }
                temp1 = temp1.next;
            }
        }
        return null;
    }
}