0%

如何判断链表有环

如何判断类似这样含有环的链表


第一种:暴力对比
第二种:借助HashSet
第三种:跑步法

暴力对比

暴力对比法是最容易想到的,每次遍历一个节点都和这个节点之前的所有节点进行比对,如果在这个节点之前有和这个节点相同的节点,那么就判定这个链表是有环的。
但是这只是个想法,在java中对象的传递大多都是引用传递,遍历要维护两个变量,还要去把值copy出来,使用代码去写不是很好写。

借助HashSet

把每个节点都放到HashSet里面,如果放不进去则说明有环。
空间复杂度为O(NB),时间复杂度为O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}