141. 环形链表#

public boolean hasCycle(ListNode head) {
    // seen：记录访问过的节点对象（按地址），用于判断是否重复到达同一节点
    Set<ListNode> seen = new HashSet<>();

    while (head != null) {
        // 若当前节点已出现过，说明沿 next 走回了旧节点，即存在环
        if (seen.contains(head)) {
            return true;
        }
        // 记录当前节点为“已访问”
        seen.add(head);
        // 沿 next 继续遍历
        head = head.next;
    }

    // 走到 null 说明链表有终点，不存在环
    return false;
}

public boolean hasCycle(ListNode head) {
    // 边界处理：空链表或仅一个节点且无后继，不可能成环
    if (head == null || head.next == null) {
        return false;
    }

    // slow：慢指针，每次走1步
    // fast：快指针，每次走2步
    ListNode slow = head;
    ListNode fast = head;

    // 当 fast 或 fast.next 为 null 时，说明走到了链表末尾（无环）
    while (fast != null && fast.next != null) {
        // 慢指针前进一步
        slow = slow.next;
        // 快指针前进两步
        fast = fast.next.next;

        // 若二者在某节点相遇，说明存在环（快指针在环内追上慢指针）
        if (slow == fast) {
            return true;
        }
    }

    // fast 无法继续前进到两步，说明无环
    return false;
}

1) 初始状态：
3 → 2 → 0 → 4
    ↑_________|
S,F
(S=slow, F=fast)

2) 第一次移动后：
3 → 2 → 0 → 4
    ↑_________|
    S   F

3) 第二次移动后：
3 → 2 → 0 → 4
    ↑_________|
        S   F

4) 最终相遇：
3 → 2 → 0 → 4
    ↑_________|
        S,F