【LeetCode 热题 100】141. 环形链表——快慢指针

Problem: 141. 环形链表
题目：给你一个链表的头节点 head ，判断链表中是否有环。

整体思路

这段代码旨在解决一个经典的链表问题：环形链表 (Linked List Cycle)。问题要求判断一个给定的单链表是否存在环，即链表中某个节点的 next 指针是否指向了它前面已经出现过的节点。

该算法采用了大名鼎鼎的 Floyd判圈算法（Floyd’s Cycle-Finding Algorithm），也常被称为 “快慢指针” 或 “龟兔赛跑” 算法。这是一种极其高效且空间优化的方法。

1. 核心思想：速度差追及

   • 算法的逻辑非常直观，就像在一个环形跑道上进行龟兔赛跑。
   • 设置两个指针，一个“慢”指针 slow 和一个“快”指针 fast，都从链表的头节点 head 出发。
   • slow 指针每次移动一步。
   • fast 指针每次移动两步。
   • 如果链表中存在环：fast 指针会先进入环，并在环内不断地绕圈。slow 指针稍后也会进入环。一旦两个指针都进入了环，fast 指针由于速度更快，它会从后面“追上”slow 指针。它们最终必然会在环内的某个节点相遇。
   • 如果链表中不存在环：fast 指针由于走得更快，它会首先到达链表的末尾（即 fast 或 fast.next 变为 null）。一旦它到达末尾，就说明整个链表已经被遍历完且没有环。

2. 算法实现步骤：

   • 初始化 slow 和 fast 指针都指向 head。
   • 进入一个 while 循环。循环的条件 fast != null && fast.next != null 是至关重要的：
     • fast != null：确保 fast 指针本身是有效的。
     • fast.next != null：确保 fast 还能再走一步（因为 fast 每次要走两步 fast.next.next）。如果这个条件不满足，说明链表已经到头了。
   • 在循环内部：
     a. 移动指针：slow = slow.next; 和 fast = fast.next.next;。
     b. 判断相遇：在移动后，立即检查 slow 和 fast 指针是否指向了同一个节点 (if (slow == fast)）。
     • 如果它们相等，说明快指针追上了慢指针，证明链表中存在环。立即返回 true。
   • 如果 while 循环正常结束（即因为 fast 到达链表末尾而终止），则说明在整个遍历过程中快慢指针没有相遇。因此，链表中不存在环，返回 false。

完整代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * 判断一个单链表是否存在环。
     * @param head 链表的头节点
     * @return 如果存在环则返回 true，否则返回 false
     */
    public boolean hasCycle(ListNode head) {
        // 初始化慢指针 slow
        ListNode slow = head;
        // 初始化快指针 fast
        ListNode fast = head;
        
        // 循环条件：只要快指针及其下一个节点不为 null，就可以继续移动
        while (fast != null && fast.next != null) {
            // 慢指针每次移动一步
            slow = slow.next;
            // 快指针每次移动两步
            fast = fast.next.next;
            
            // 核心判断：如果快慢指针相遇，则证明存在环
            if (slow == fast) {
                return true;
            }
        }
        
        // 如果循环结束，说明快指针到达了链表末尾，不存在环
        return false;
    }
}

时空复杂度

时间复杂度：O(N)

1. 无环情况：如果链表没有环，快指针 fast 会先到达链表末尾。它走过的节点数大约是 N，而慢指针 slow 走了 N/2。总的来说，算法对链表进行了一次线性扫描。时间复杂度为 O(N)。
2. 有环情况：
   • 设链表头到环入口的长度为 A，环的长度为 C。
   • 当慢指针到达环入口时，它走了 A 步。此时，快指针已经在环内走了 A 步。
   • 此时，快指针相对于慢指针在环内的位置领先 A % C 步。
   • 慢指针需要被快指针追上。快指针每走一步，与慢指针的距离缩小 1。要追上 C - (A % C) 的距离，最多需要 C 步。
   • 因此，总的步数大约是 A (慢指针入环) + C (在环内追及)，即 A+C。由于 A+C <= N，所以时间复杂度仍然是 O(N)。

综合分析：
无论链表是否有环，算法的时间复杂度都与链表的节点数 N 成线性关系，即 O(N)。

空间复杂度：O(1)

1. 主要存储开销：该算法没有创建任何与输入规模 N 成比例的新的数据结构。
2. 辅助变量：只使用了 slow 和 fast 两个指针变量来遍历链表。这些变量的数量是固定的，与链表长度无关。

综合分析：
算法所需的额外辅助空间是常数级别的。因此，其空间复杂度为 O(1)。这是解决此问题最优的空间效率。