Algorithm|LinkedList

快慢指针

判断环

141.环形链表

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。

为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。

注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

第一思路:存储访问Map

第一眼想到的是用一个Map存储是否已经访问的状态

在一次遍历的过程中更新这个Map

如果存在环,那么一定会再次访问Map中相同的节点,这个时候就可以以此来进行判断了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
Map<ListNode, Boolean> visited = new HashMap<>();
ListNode curr = head;
while (curr.next != null) {
if (Boolean.TRUE.equals(visited.get(curr))) {
return true;
}
visited.put(curr, true);
curr = curr.next;
}
return false;
}

进阶思路:快慢指针

这是经典的Floyd判圈算法,原理很简单:我们手动设定两个指针,一快一慢,如果存在环,那么一定会有某个时刻,快的重新追上慢的

原理虽然简单,但是带来的效果很强大,他解决了我们第一种情况下O(n)空间复杂度的问题,只实现了常量级(O(2))的内存,就实现了一样的效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 快慢指针Floyd判圈算法
* @param head 头结点
* @return 是否有环
*/
public boolean floydCircleCheck(ListNode head) {
//0个节点或者是1个节点都可以认为没有环
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
//如果没有环,fast一定走到了终点
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
//有环,快的一定会在某一轮次追上慢的
return true;
}

Algorithm|LinkedList
http://example.com/2025/07/18/Algorithm-LinkedList/
作者
Noctis64
发布于
2025年7月18日
许可协议