共计 4065 个字符，预计需要花费 11 分钟才能阅读完成。
对于求有环无环单链表相交的问题，是链表类型题目中首屈一指的难题，且听一一道来。
一、题目形容
给定两个可能有环也可能无环的单链表，头节点 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…
