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

一、题目形容

给定两个可能有环也可能无环的单链表，头节点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...