链表节点定义如下
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
对应的情况如下
明确了链表存在环的形式之后
判断是否存在环就变的非常简单了
如果存在环
则依次遍历链表的每个节点
必然没有最终的节点
且会不断重复遍历环内的所有节点
如果不存在环
则依次遍历链表的每一个节点
最终必然会得到一个null节点
所以最简单的办法就是:
使用一个集合存储遍历过的节点
如果发现有重复的节点,则就是存在环
且第一次出现重复节点的地方,就是环的入口节点
如果遍历的过程中出现了null节点,则就是不存在环
第一种思路很好理解
也很好实现
直接上代码
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;
}
第一种解法的时间复杂度位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节点也刚好走到环的入口节点
那么就找到环的入口节点了
判断是否存在环
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日