判断链表是否有环的解法有很多，下面归纳几种常见算法。
判断链表是否存在环
方法一：
通过双循环遍历完成，外层循环从头结点开始遍历，对于遍历到一个新节点newNode，内层循环都要从头结点遍历到该新节点的上一个节点head。如果链表无环，则newNode和head永不相等，否则就会相等。时间复杂度为O(n^2)。
public class LinkListCycle {
public static class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
}
}
public static void main(String[] args) {
Node node1 = new Node(5);
Node node2 = new Node(3);
Node node3 = new Node(7);
Node node4 = new Node(2);
Node node5 = new Node(6);
Node node6 = new Node(8);
Node node7 = new Node(1);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node7;
node7.next = node7;
LinkListCycle linkListCycle = new LinkListCycle();
linkListCycle.hasCycleForMethodOne(node1);
System.out.println(linkListCycle.getCycleLength(node1));
}
//判断是否存在环，双重遍历，时间复杂度为O(n^2)
public boolean hasCycleForMethodOne(Node node) {
//外部遍历新节点
Node newNode = node;
while (newNode != null) {
//从头节点遍历到新节点的上一个节点
Node head = node;
while (head != null && head.next != newNode) {
if (head == newNode) {
return true;
}
head = head.next;
}
newNode = newNode.next;
}
return false;
}
}
方法二：
使用HashMap（或者HashSet），以Node节点作为key，遍历链表，如果node节点不存在则添加到集合中，如果节点存在则说明有环。时间复杂度为O(n)，空间复杂度为O(n)。
//使用map查找环，时间复杂度为O(n)，空间复杂度为O(n)
public boolean hasCycleForMethodTwo(Node node) {
Map<Node, Integer> map = new HashMap<>();
while (node != null) {
if (!map.containsKey(node)) {
map.put(node, 1);
} else {
//此时的node即为环的入口
System.out.println(node);
return true;
}
node = node.next;
}
return false;
}
方法三：
快慢指针。类似于数学中的追及问题，设置一个快指针，步长为2，设置一个慢指针，步长为1。如果不存在环，则快慢指针不会相遇。如果存在环，则快慢指针会相遇。时间复杂度为O(n)，空间复杂度为O(1)。
此为最优方法
//使用快慢指针查找环,时间复杂度为O(n)，空间复杂度为O(1)
public boolean hasCycleForMethodThree(Node node) {
//快指针，每次走2步
Node fast = node;
//慢指针，每次走1步
Node low = node;
while (fast != null && fast.next != null) {
fast = fast.next.next;
low = low.next;
//快慢指针相遇，存在环
if (fast == low) {
return true;
}
}
return false;
}
求环的长度
方法一：
使用HashMap，对环进行多次遍历。
//查找环的长度
public int getCycleLength(Node node) {
Map<Node, Integer> map = new HashMap<>();
int count = 0;
while (node != null) {
if (!map.containsKey(node)) {
map.put(node, 1);
} else {
map.put(node, map.get(node) + 1);
}
//对环进行第二遍遍历
if (map.get(node) == 2) {
count++;
}
//对环第三遍遍历
if (map.get(node) == 3) {
break;
}
node = node.next;
}
return count;
}
方法二：
以指针第一次相遇为起点，记录第二次相遇时的步数即为环的长度。
public int getCycleLength(Node node) {
//快指针，每次走2步
Node fast = node;
//满指针，每次走1步
Node low = node;
//指针是否相遇
boolean first = false;
//环的长度
int count = 0;
while (fast != null && fast.next != null) {
fast = fast.next.next;
low = low.next;
if (first) {
count++;
}
//快慢指针相遇，存在环
if (fast == low) {
if (first) {
//第二次相遇
return count;
} else {
//第一次相遇
first = true;
}
}
}
return -1;
}
求环的入口
方法一：
见判断链表是否存在环#方法二。
方法二：
设D为从头节点到入环点的步长，逆时针方向，s1为入环点到首次相遇点的步长，s2为从首次相遇点到入环点的步长。在相遇点快慢指针走过的距离为：
2(D+S1 ) = D+S1 +n(S1 +S2 )–>D = (n-1)(S1 +S2 )+S2
即从链表头结点到入环点的距离，等于从首次相遇点绕环n-1圈再回到入环点的距离。这样一来，只要把其中一个指针放回到头节点位置，另一个指针保持在首次相遇点，两个指针都是每次向前走1步。那么，它们最终相遇的节点，就是入环节点。
public Node getCycleEntrance(Node node) {
//快指针，每次走2步
Node fast = node;
//满指针，每次走1步
Node low = node;
boolean hasCycle = false;
//获取第一次相遇节点fast
while (fast != null && fast.next != null) {
fast = fast.next.next;
low = low.next;
//快慢指针相遇，存在环
if (fast == low) {
hasCycle = true;
break;
}
}
//无环直接返回
if (!hasCycle) {
return null;
}
//指向头节点
Node head = node;
//指向第一次相遇节点
Node counter = fast;
while (head != null && counter != null) {
if (head == counter) {
return head;
}
head = head.next;
counter = counter.next;
}
return null;
}