如何判断两个有环链表是否相交

如何判断两个有环链表是否相交

问题

​ 如何判断两个有环链表是否相交，相交则返回第一个相交节点，不相交则返回null。

思路

​ 我们已经得到了两个链表各自的第一个入环节点，假设链表1的第一个入环节点为loop1，链表2的第一个入环节点为loop2。具体如下：

​ 1.如果loop1 == loop2，拓扑结构如图：

​ 该情况下，考虑链表1从头开始到loop1这一段与链表2从头开始到loop2这一段，在哪里第一次相交即可。这与判断两个无环链表是否相交类似，只是这里把loop1(loop2)作为判断终止条件。

​ 2.如果loop1 != loop2，两个链表不相交的拓扑结构如图：

case1	case2

​ 需要分辨是哪种情况，进入步骤3。

​ 3.让链表1从loop1出发，因为loop1和之后节点都在环上，所以将来一定能回到loop1。如果回到loop1之前并没有遇到loop2，那么将是case1，也就是不相交，返回null。否则是case2，也就是相交。因为loop1和loop2都在两条链表上，此时返回loop1或loop2都可以。

代码

public Node bothLoop(Node head1, Node loop1, Node head2, Node loop2){
    Node cur1 = null;
    Node cur2 = null;
    if (loop1 == loop2){
        cur1 = head1;
        cur2 = head2;
        int n = 0;
        while (cur1 != loop1){
            n++;
            cur1 = cur1.next;
        }
        while (cur2 != loop2){
            n--;
            cur2 = cur2.next;
        }
        cur1 = n > 0?head1:head2;
        cur2 = cur1 == head1?head2:head1;
        n = Math.abs(n);
        while (n != 0){
            n--;
            cur1 = cur1.next;
        }
        while (cur1 != cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    } else {
      cur1 = loop1.next;
        while (cur1 != loop1){
            if (cur1 == loop2){
                return loop1;
            }
            cur1 = cur1.next;
        }
        return null;
    }
}