题解 | #判断链表中是否有环#

判断链表中是否有环

目标

我们需要判断一条项链（链表）是不是闭合成圈的。如果是闭合成圈的，我们就说这条项链有“环”，并返回 true；如果没有闭合成圈，我们就说这条项链没有“环”，并返回 false。

示例

假设我们有两条项链：

• 第一条项链：3 → 2 → 0 → -4，并且 -4 指向第 2 个珠子（形成环）。
• 第二条项链：1，没有任何珠子指向其他珠子（没有环）。

解释步骤

1. 准备两个“兔子”

想象一下，我们有两个“兔子”，一个跑得慢，一个跑得快。慢兔子每次跳一步，快兔子每次跳两步。

ListNode slow = head; // 慢兔子
ListNode fast = head; // 快兔子

2. 让兔子开始跑

让两个兔子从项链的起点开始跑。慢兔子每次跳一步，快兔子每次跳两步。

while (fast != null && fast.next != null) {
    slow = slow.next; // 慢兔子跳一步
    fast = fast.next.next; // 快兔子跳两步
}

3. 观察兔子

如果项链有环，快兔子最终会追上慢兔子。如果项链没有环，快兔子会一直跑到项链的尽头（null）。

if (slow == fast) {
    return true; // 如果快兔子追上了慢兔子，说明有环
}

4. 结果

如果快兔子跑到了项链的尽头，说明项链没有环，返回 false。

return false; // 如果快兔子跑到尽头，说明没有环

示例解析

示例 1

输入：{3,2,0,-4},1

1. 初始化兔子：
1. 慢兔子和快兔子都站在 3 上。
2. 让兔子跑：
1. 慢兔子跳到 2，快兔子跳到 0。
2. 慢兔子跳到 0，快兔子跳到 -4。
3. 慢兔子跳到 -4，快兔子跳回 2（因为 -4 指向 2）。
3. 观察兔子：
1. 快兔子追上了慢兔子，说明有环。
4. 结果：
1. 返回 true。

示例 2

输入：{1},-1

1. 初始化兔子：
1. 慢兔子和快兔子都站在 1 上。
2. 让兔子跑：
1. 快兔子跑到项链的尽头（null）。
3. 观察兔子：
1. 快兔子没有追上慢兔子，说明没有环。
4. 结果：
1. 返回 false。

示例 3

输入：{-1,-7,7,-4,19,6,-9,-5,-2,-5},6

1. 初始化兔子：
1. 慢兔子和快兔子都站在 -1 上。
2. 让兔子跑：
1. 慢兔子跳到 -7，快兔子跳到 -4。
2. 慢兔子跳到 7，快兔子跳到 -5。
3. 慢兔子跳到 -4，快兔子跳到 -5。
4. 慢兔子跳到 19，快兔子跳到 -5。
5. 慢兔子跳到 6，快兔子跳到 -5。
6. 慢兔子跳到 -9，快兔子跳到 -5。
7. 慢兔子跳到 -5，快兔子跳到 -5。
3. 观察兔子：
1. 快兔子追上了慢兔子，说明有环。
4. 结果：
1. 返回 true。

最后附上完整代码

public class Solution {
    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) {
            if (slow == fast) {
                return true; // 如果快慢指针相遇，说明有环
            }
            slow = slow.next; // 慢指针向前一步
            fast = fast.next.next; // 快指针向前两步
        }

        return false; // 如果快指针到达尾部，说明没有环
    }
}