暴力思路：可以直接使用set记录下节点的地址值，如果有重复那么就是有环，如果指针走到了最后那么就说明无环
1
2
3
4
5
6
7
8
9
10
11
| public boolean hasCycle(ListNode head) {
Set set = new HashSet<>();
while (head != null) {
if(!set.contains(head)){
set.add(head);
}else
return true;
head=head.next;
}
return false;
}
|
双指针思路:使用快慢指针,如果快指针和慢指针相撞，就说明有环，如果快指针走到头，就说明无环
1
2
3
4
5
6
7
8
9
10
11
12
13
| public boolean hasCycle(ListNode head) {
ListNode fast =head;
ListNode slow =head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
return true;
}
}
return false;
}
|
142环形链表II
与141环形链表1相比,使用set的方法很明显更简单更快捷,而使用双指针则需要一点点数学能力
思路: 假设有环,那么fast一定会走slow的两倍。设slow为k，fast为2k。
我们假设相遇点距离环的起点为m,那么环起点距离头节点为k-m，而在环内的fast走k-m也能到环起点，也就是说当两者相遇的时候k-m就是起点了
图片源自:labuladong.online
双指针解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast.next.next!=null&&fast.next!=null){
slow = slow.next;
fast=fast.next.next;
if(fast==slow){
slow=head;
break;
}
}
int count =0;
if(fast==slow){
while(fast!=slow){
count++;
fast=fast.next;
slow=slow.next;
}
return count;
}
return null;
}
|