必会算法：判断链表有环并找出环入口
链表节点定义如下
public class Node {
public Integer value;
public Node next;
public Node() {
}
public Node(Integer value) {
this.value = value;
}
public Node(Integer value, Node next) {
this.value = value;
this.next = next;
}
@Override
public String toString() {
Node temp = this;
StringBuilder str = new StringBuilder();
while (temp != null) {
str.append(temp.value).append("->");
temp = temp.next;
}
str.append("null");
return str.toString();
}
public String toStringWhenCircle() {
Node temp = this;
StringBuilder str = new StringBuilder();
Set<Integer> set = new HashSet<>();
while (temp != null && !set.contains(temp.value)) {
str.append(temp.value).append("->");
set.add(temp.value);
temp = temp.next;
}
if (temp != null) {
str.append(temp.value);
}
return str.toString();
}
}题目
给定一个链表，判断链表中是否存在环
如果存在环，请给出环的入口节点
解题
首先我们需要明确
链表存在环是什么情况
其中L部分的长度最短为0
对应的情况如下
而C部分的长度最短为1
对应的情况如下
明确了链表存在环的形式之后
判断是否存在环就变的非常简单了
思路1
如果存在环
则依次遍历链表的每个节点
必然没有最终的节点
且会不断重复遍历环内的所有节点
如果不存在环
则依次遍历链表的每一个节点
最终必然会得到一个null节点
所以最简单的办法就是：
使用一个集合存储遍历过的节点
如果发现有重复的节点，则就是存在环
且第一次出现重复节点的地方，就是环的入口节点
如果遍历的过程中出现了null节点，则就是不存在环
代码实现1
第一种思路很好理解
也很好实现
直接上代码
public static Boolean isLinkedCircle(Node list) {
if (list == null || list.next == null) {
return false;
}
HashSet<Node> nodeHashSet = new HashSet<>();
Node header = list;
// 当第二次遍历到环入口的时候，则跳出循环
while (nodeHashSet.add(header)) {
header = header.next;
if (header == null) {
return false;
}
}
return true;
}找到环入口的代码
public static Node findLinkedCircle(Node list) {
if (list == null || list.next == null) {
return null;
}
HashSet<Integer> nodeHashSet = new HashSet<>();
// 当第二次遍历到环入口的时候，则跳出循环
while (nodeHashSet.add(list.value)) {
list = list.next;
if (list == null) {
return null;
}
}
return list;
}思路2
第一种解法的时间复杂度位O(n)
但是由于用到了集合
所以会消耗额外的空间
所以有没有减少空间损耗的办法呢？
让我们回到一道小学数学题
小明上学又忘了拿作业了
小明妈妈怎么才能追上去把作业给他呢？
很简单，如果距离足够远
那么只要小明妈妈比小明走的快
就一定能追上
所以针对链表是否存在环的问题
我们可以使用两个不同速度的指针遍历链表
假设快指针是慢指针速度的两倍
也就是快指针一次走两个节点
慢指针一次走一个节点
如果不存在环
那么慢指针肯定永远无法追上快指针
并且快指针很快就变成了null
如果存在环
那么在环中循环的时候
因为快慢指针的速度差
快指针肯定会实现套圈
并追上慢指针
所以只要快慢指针一相遇，就必然存在环
但是如何求出环的入口节点呢？
这个链表比较特殊，第一次的相交点刚好是环的入口节点
实际情况是第一次的相交节点可能在环的任何位置
我们可以简化为一下图案
其中
a：表示链表非环部分的长度
b：表示环入口到第一次相交点的长度
c：表示第一次相交点到环入口的长度
因为快指针的速度是慢指针的两倍
所以第一次相交的时候
慢指针肯定没有走完一个完整的环
由此可以得出以下两个公式：
快指针走过的长度Sfaster=a+n*(b+c)+b
其中n>=1，表示快指针已经绕过的环数
慢指针走过的长度Sslower=a+b
而快指针的速度是慢指针的两倍
所以Sfaster=2*Sslower
代入上边的公式可得
a+n(b+c)+b = 2(a+b)
→a=n（b+c）-b
→a=（n-1）*（b+c）+c
其中b+c就是环的长度
此时如果有一个指针header从链表头部开始以速度1进行遍历
faster或者slower指针从相交点以速度1进行遍历
因为a=（n-1）*（b+c）+c；n>=1
所以header走到环入口节点的时候
faster或者slower节点也刚好走到环的入口节点
那么就找到环的入口节点了
代码实现2
判断是否存在环
public static Boolean isLinkedCircle2(Node list) {
if (list == null || list.next == null) {
return false;
}
Node faster = list.next.next;
Node slower = list.next;
while (faster != slower) {
if (faster == null || faster.next == null) {
return false;
}
// faster指针一次走两下
faster = faster.next.next;
// slower指针一次走一下
slower = slower.next;
}
return true;
}找出环的入口节点
public static Node findLinkedCircle2(Node list) {
if (list == null || list.next == null) {
return null;
}
Node faster = list.next.next;
Node slower = list.next;
while (faster != slower) {
if (faster == null || faster.next == null) {
return null;
}
faster = faster.next.next;
slower = slower.next;
}
// 让另一个指针从链表头开始遍历
// 让faster或者slower从相交点同步遍历
// 他们再次的相交点就是环的入口节点
while (faster != list) {
faster = faster.next;
list = list.next;
}
return faster;
}测试验证
public static void main(String[] args) {
Node list = new Node(1);
Node temp = list;
Node cross = null;
for (int i = 2; i < 10; i++) {
temp.next = new Node(i);
temp = temp.next;
if (i == 5) {
cross = temp;
}
}
// 在节点5的位置制造一个环
temp.next = cross;
System.out.printf("链表[%s]是否存在环：%s\n", list.toStringWhenCircle(), isLinkedCircle(list));
System.out.printf("链表[%s]是否存在环：%s\n", list.toStringWhenCircle(), isLinkedCircle2(list));
System.out.printf("链表[%s]存在环的入口节点：%d\n", list.toStringWhenCircle(), findLinkedCircle(list).value);
System.out.printf("链表[%s]存在环的入口节点：%d\n", list.toStringWhenCircle(), findLinkedCircle2(list).value);
}
文/戴先生@2022年02月13日
腾讯云开发者
