共计 1136 个字符，预计需要花费 3 分钟才能阅读完成。
前面，我们实现了链表的 反转 操作，本篇来聊聊，如何检测单链表中的环。
链表环检测
Leetcode 141: Linked List Cycle
有两种方法来解决这个问题：
使用 Hashing
思路
定义一个 Map，当循环遍历 Linked List 时，依次将 Node 放入 Map 中，等到循环到下一轮时，检查 Node 是否存在于 Map 中，若存在则表示有环存在。
实现
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
Map map = new IdentityHashMap();
for(ListNode x = head; x != null;){
if(map.containsKey(x)){
return true;
}
map.put(x, null);
x = x.next;
}
return false;
}
}
Floyd 判圈算法
Floyd 判圈算法如果有限状态机、迭代函数或者链表上存在环，那么在某个环上以不同速度前进的 2 个指针)必定会在某个时刻相遇。同时显然地，如果从同一个起点 (即使这个起点不在某个环上) 同时开始以不同速度前进的 2 个指针最终相遇，那么可以判定存在一个环，且可以求出 2 者相遇处所在的环的起点与长度。
从 Linked List 的 Head 节点出发，我们定义两个移动指针，一个的移动速度为每次前进一个节点，另一个每次前进两个节点。然后判断这两个指针移动后的结果是否相等。
代码
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
}
这两种方式的时间复杂度均为 O(n)，空间复杂度均为 O(1).
参考资料
https://www.geeksforgeeks.org…
https://marcin-chwedczuk.gith…
Floyd 判圈算法
《数据结构与算法之美》
