如何判断类似这样含有环的链表
第一种：暴力对比
第二种：借助HashSet
第三种：跑步法
暴力对比
暴力对比法是最容易想到的，每次遍历一个节点都和这个节点之前的所有节点进行比对，如果在这个节点之前有和这个节点相同的节点，那么就判定这个链表是有环的。
但是这只是个想法，在java中对象的传递大多都是引用传递，遍历要维护两个变量，还要去把值copy出来，使用代码去写不是很好写。
借助HashSet
把每个节点都放到HashSet里面，如果放不进去则说明有环。
空间复杂度为O(NB),时间复杂度为O(N)
class Node {
Object value;
Node next;
public Node(Object value) {
this.value = value;
}
}
boolean hasCycle(Node node) {
HashSet<Object> temp = new HashSet<>();
while (node.next != null){
if(!temp.add(node.value)){
return true;
}
node = node.next;
}
return false;
}
跑步法
维护两个指针，A指针一次跳一个，B指针一次跳两个，如果有环的话那么B指针就会和A指针相遇，如果没有就直接遍历结束。
空间复杂度为O(1),时间复杂度为O(N)
class Node {
Object value;
Node next;
public Node(Object value) {
this.value = value;
}
}
boolean hasCycle(Node node) {
if (node == null || node.next == null) {
return false;
}
Node slow = node;
Node fast = node.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
