当前位置：首页 > Java

java如何确认环

2026-03-24 22:12:50Java

检测链表中的环

在Java中检测链表是否存在环，通常使用快慢指针法（Floyd's Cycle Detection Algorithm）。该方法通过两个指针以不同速度遍历链表，若存在环，快指针最终会追上慢指针。

实现步骤：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

关键点：

初始化慢指针 slow 指向头节点，快指针 fast 指向头节点的下一个节点。
每次迭代中，慢指针移动一步，快指针移动两步。
如果快指针遇到 null，说明链表无环；若快慢指针相遇，则存在环。

数学证明

假设链表环外部分长度为 a，环内部分长度为 b。快指针每次走两步，慢指针每次走一步，两者速度差为1。当慢指针进入环后，快指针最多需要追赶 b-1 步即可相遇，因此时间复杂度为 O(n)。

替代方法：哈希表

另一种方法是使用哈希表记录已访问的节点：

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        while (head != null) {
            if (visited.contains(head)) {
                return true;
            }
            visited.add(head);
            head = head.next;
        }
        return false;
    }
}

优缺点：

java如何确认环