对于求有环无环单链表相交的问题，是链表类型题目中首屈一指的难题，且听一一道来。

一、题目形容

给定两个可能有环也可能无环的单链表，头节点 head1 和 head2。

请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回 null

要求：如果两个链表长度之和为 N，工夫复杂度请达到 O(N)，额定空间复杂度请达到 O(1)。

二、思路

解决思路分为两大步：

（1）找到单链表的入环节点，无环则返回 null

（2）依据失去的链表的入环节点，再展开讨论

1、找到单链表的入环节点，无环则返回 null

（1）遍历此单链表，如果某次遍历到的节点为 null，则此单链表必然无环

（2）否则有环

筹备一个快指针，一个慢指针。开始时，两个指针都从头节点开始，快指针一次走两个节点，慢指针一次走一个节点，直到两个指针相遇。

此时，快指针再从头节点开始走，每次走一个节点；慢指针从相遇处持续往下走，仍然一次走一个节点，当两个指针再次相遇时的节点即是入环节点。

2、依据失去的链表的入环节点，再展开讨论

（1）两个链表都无环

遍历其中一个链表，记录链表的长度 length1 和最初一个节点 end1；遍历另外一个链表，记录链表的长度 length2 和最初一个节点 end2。

如果 end1 和 end2 不等，则两个链表肯定不相交；否则，计算 length1 和 length2 的差值 a，长链表先走 a 个节点，而后两个链表挨个往下走，第一个相等的节点即是相交的第一个节点。

（2）一个有环、一个无环

此种状况两个链表是不可能相交的。（大伙能够尝试脑补出这样的构造， 记住一点，是单链表 ）

（3）两个链表都有环

分三种状况，各自有环然而不相交；入环节点是同一个；入环节点有两个。

1）各自有环然而不相交

2）入环节点是同一个

3）入环节点有两个

两个链表的入环节点相等：即入环节点是同一个这种状况，求解过程和两个链表都是无环且相交的过程是一样的，也就是求解时齐全能够疏忽前面的环。

两个链表的入环节点不等：则是第一小种或第三小种。此时，从其中一个入环节点开始，遍历一圈，如果在回到本人时遇到了第二个入环节点，则是第三小种，否则就是第一小种。

三、具体参考代码

1、找到单链表的入环节点

/**
 * 找到单链表的入环节点，无环则返回 null
 *
 * @author Java 和算法学习：周一
 */
public static Node getLoopNode(Node head) {if (head == null || head.next == null || head.next.next == null) {return null;}
    // 快指针
    Node fast = head.next.next;
    // 慢指针
    Node 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;
}

2、依据失去的链表的入环节点，再展开讨论

（1）两个链表都无环

/**
 * 当初曾经晓得两个链表无环，找到它们的第一个相交节点
 *
 * @author Java 和算法学习：周一
 */
public static Node noLoop(Node head1, Node head2) {if (head1 == null || head2 == null) {return null;}

    Node current1 = head1;
    Node current2 = head2;
    int n = 0;
    // 链表一遍历一遍失去长度、最初一个节点
    while (current1.next != null) {
        n++;
        current1 = current1.next;
    }

    // 链表二遍历一遍失去长度差、最初一个节点
    while (current2.next != null) {
        n--;
        current2 = current2.next;
    }

    // 如果两个链表的最初一个节点不等，则肯定不相交
    if (current1 != current2) {return null;}

    // 长链表的头节点给 current1
    current1 = n > 0 ? head1 : head2;
    // 短链表的头节点给 current2
    current2 = current1 == head1 ? head2 : head1;

    n = Math.abs(n);
    // 长链表先走 n 个节点
    while (n != 0) {
        n--;
        current1 = current1.next;
    }

    // 两个链表挨个往下走，第一次相等的节点即是第一个相交的节点
    while (current1 != current2) {
        current1 = current1.next;
        current2 = current2.next;
    }

    return current1;
}

（3）两个链表都有环

/**
 * 两个链表都有环
 * 分三种状况，各自有环然而不相交；入环节点是同一个；入环节点有两个     
 *
 * @author Java 和算法学习：周一
 */
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
    Node current1 = null;
    Node current2 = null;
    if (loop1 == loop2) {
        current1 = head1;
        current2 = head2;
        int n = 0;
        // 计算 head1 链表有多少个节点
        while (current1 != loop1) {
            n++;
            current1 = current1.next;
        }

        // 计算两个链表节点数的差值
        while (current2 != loop2) {
            n--;
            current2 = current2.next;
        }

        // 长链表的头节点给 current1
        current1 = n > 0 ? head1 : head2;
        // 短链表的头节点给 current2
        current2 = current1 == head1 ? head2 : head1;

        n = Math.abs(n);
        // 长链表先走 n 个节点
        while (n != 0) {
            current1 = current1.next;
            n--;
        }

        // 两个链表挨个往下走，第一次相等的节点即是第一个相交的节点
        while (current1 != current2) {
            current1 = current1.next;
            current2 = current2.next;
        }

        return current1;
    } else {
        // 两个链表的入环节点不等，则是各自有环然而不相交或者入环节点有两个
        current1 = loop1.next;
        // 从其中一个入环节点开始，遍历一圈，如果在回到本人时遇到了第二个入环节点，则是 入环节点有两个
        while (current1 != loop1) {if (current1 == loop2) {
                // 此时两个入环节点都是第一个相交节点，返回其中一个即可
                return loop1;
            }
            current1 = current1.next;
        }
        return null;
    }
}

以上是外围具体参考代码，置信主办法和测试方法可能轻易的写进去，当然想参考全副代码，此处也附上本文全副代码的 Github 地址：

https://github.com/monday-pro…