链表简单2 种解法

#141环形链表

判断单链表中是否存在沿 next 可重复到达的环。

#链表#哈希表#双指针

解题主线

哈希法直接检测节点对象是否再次出现，比较的是节点身份而不是节点值。

Floyd 算法中快指针每次走两步；若有环，它最终一定在环内追上慢指针。

解法 1：节点集合

遍历时把每个节点对象放入集合；首次遇到已存在的对象即可判定有环。

时间复杂度

O(n)

空间复杂度

O(n)

141. 环形链表 · 节点集合

java

import java.util.Collections;
import java.util.IdentityHashMap;
import java.util.Set;

public class Solution {
    static final class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = Collections.newSetFromMap(new IdentityHashMap<>());
        for (ListNode current = head; current != null; current = current.next) {
            if (!seen.add(current)) return true;
        }
        return false;
    }
}

遍历时把每个节点对象放入集合；首次遇到已存在的对象即可判定有环。

解法 2：Floyd 快慢指针

slow 每次走一步、fast 每次走两步；二者相遇表示有环，fast 到达 null 表示无环。

时间复杂度

O(n)

空间复杂度

O(1)

141. 环形链表 · Floyd 快慢指针

java

public class Solution {
    static final class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    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;
    }
}

slow 每次走一步、fast 每次走两步；二者相遇表示有环，fast 到达 null 表示无环。

边界与易错点

不能按 val 去重，不同节点可以有相同值。
旧文件中的 hasCycle1 与 hasCycle2 完全重复，合并后只保留一个 Floyd 解法。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

Q141_cycleLinkedList.javaQ141_hasCycle.java