如何判断一个单链表是否有环？

要判断一个单链表是否有环,可以使用快慢指针算法。

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) return false;

    ListNode slow = head; 
    ListNode fast = head.next;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }

    return false;
}

算法流程:

1. 先判断链表是否为空或只有一个节点,如果是则返回 false。
2. slow 指针每次移动一步,fast 指针每次移动两步。
3. 如果 fast 指针能够追上 slow 指针,则链表有环,返回 true。
4. 如果 fast 指针移动至链表尾部,则链表无环,返回 false。

例如:
有环链表: A -> B -> C -> D -> E -> C
无环链表: A -> B -> C -> D -> E -> null
对有环链表,当 fast 指针移动到 C 时,slow 指针也在 C,所以相遇,返回 true。
对无环链表,当 fast 指针移动至 E,slow 指针在 D,fast 继续移动至 null,所以未相遇,返回 false。

所以,判断链表是否有环的关键在于:

1. 使用快慢指针,慢指针每次移动一步,快指针每次移动两步。
2. 如果快指针能够追上慢指针,则链表有环,否则无环。
3. 特殊情况,如果链表为空或只有一个节点,直接返回 false。