力扣hot100:环形链表（快慢指针法）（141）

一、题目描述

二、思路分析

这是链表题目中的经典问题，核心就是 如何判断链表是否有环。
常见的两种方法有：

1. 哈希表法：用一个集合存储访问过的节点，如果再次遇到相同节点说明有环。

   • 缺点：需要额外的空间，空间复杂度 O(n)。

2. 快慢指针法（Floyd 判圈算法）：通过两个速度不同的指针在链表中移动，如果存在环，那么快指针一定会在环中追上慢指针。

   • 优点：只需常数空间，空间复杂度 O(1)。

   • 这也是本题的最优解。

你的代码实现采用了第二种方法，也就是 快慢指针法。

三、代码讲解

下面是我的实现代码：

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;

            if (slow == fast) {
                return true;
            }
        }

        return true;
    }
}

1. 边界条件

if (head == null || head.next == null) {
    return false;
}

如果链表为空，或者只有一个节点（且没有环），那么显然不可能存在环，直接返回 false。

2. 初始化快慢指针

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

• slow 每次走一步；

• fast 每次走两步。
  这样设计可以保证在有环的情况下，快指针一定会在环中追上慢指针。

3. 循环遍历

while (slow != fast) {
    if (fast == null || fast.next == null) {
        return false;
    }
    slow = slow.next;
    fast = fast.next.next;

    if (slow == fast) {
        return true;
    }
}

• 如果快指针走到 null，说明链表没有环（因为如果有环，快指针永远不会走到尽头）。

• 如果 slow == fast，则说明快慢指针在环中相遇，即链表存在环。

4. 返回结果

最终，如果跳出 while 循环，说明 slow == fast，返回 true。

四、复杂度分析

• 时间复杂度：O(n)

  • 最坏情况下，快慢指针要遍历链表的所有节点，复杂度为线性级别。

• 空间复杂度：O(1)

  • 只用了两个指针变量，不需要额外存储空间。

五、总结

• 本题是典型的 快慢指针 应用场景。

• 通过设置不同速度的指针来判断是否存在环，大大节省了空间。

• 此题也是后续 环形链表 II（寻找环的入口节点）的基础。

✨ 总结一句话：
在链表问题里，如果涉及到“是否存在环”，首先考虑快慢指针。