pexels-photo-589810

前面，我们实现了链表的 反转 操作，本篇来聊聊，如何检测单链表中的环。

单链表环检测

Leetcode 141. Linked List Cycle

有两种方法来解决这个问题：

使用 Hashing

思路

定义一个 Map，当循环遍历 Linked List 时，依次将 Node 放入 Map 中，等到循环到下一轮时，检查 Node 是否存在于 Map 中，若存在则表示有环存在。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 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 节点出发，我们定义两个移动指针，一个的移动速度为每次前进一个节点，另一个每次前进两个节点。然后判断这两个指针移动后的结果是否相等。

这就类似于两个人在操场上的跑步一样，一个快，一个慢，他们总会在某一个位置相遇。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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).

相关练习

参考资料