LeetCode 141. 环形链表 [Hot 100] —— 龟兔赛跑算法

141. 环形链表

简单

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

方法一：哈希表

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head!=null) {
            if (set.contains(head)) return true;
            set.add(head);
            head=head.next;
        }
        return false;
    }
}

方法二：快慢指针算法

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

龟兔赛跑算法（Floyd判圈算法）

龟兔赛跑算法（Floyd's Cycle-Finding Algorithm），也称为快慢指针算法，是一种用于检测链表中环的存在并找到环起点的经典算法。

算法原理

1. 检测环的存在

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    
    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;  // 兔子走到尽头说明无环
}

2. 找到环的起点

public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    boolean hasCycle = false;
    
    // 第一阶段：检测环
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }
    
    if (!hasCycle) return null;
    
    // 第二阶段：找到环起点
    slow = head;  // 乌龟回到起点
    while (slow != fast) {
        slow = slow.next;  // 两者都每次走一步
        fast = fast.next;
    }
    
    return slow;  // 相遇点即为环起点
}

数学证明

为什么能检测环？

• 如果无环：兔子会先到达终点（null）
• 如果有环：兔子和乌龟最终会在环内相遇

为什么能找到环起点？

设：

• 链表头到环起点距离：a
• 环起点到相遇点距离：b
• 相遇点到环起点距离：c
• 环长度：L = b + c

当第一次相遇时：

• 乌龟走的距离：a + b
• 兔子走的距离：a + b + n*L（多绕了n圈）

因为兔子速度是乌龟的2倍：

2(a + b) = a + b + n*L
a + b = n*L
a = n*L - b = (n-1)*L + c

所以从链表头和相遇点同时出发，会在环起点相遇。

应用场景

1. 检测链表是否有环
2. 找到环的起点
3. 计算环的长度（相遇后让一个指针不动，另一个走一圈计数）
4. 计算链表总长度（环长度 + 非环部分长度）

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)（只用了两个指针）

示例

链表：1 → 2 → 3 → 4 → 5 → 3（形成环，环起点是3）

步骤：
1. 龟(1)兔(1) → 龟(2)兔(3) → 龟(3)兔(5) → 龟(4)兔(4) ← 相遇
2. 龟回到起点(1)，兔在相遇点(4)
3. 龟(1)→(2)，兔(4)→(5)→(3) ← 还没相遇
4. 龟(2)→(3)，兔(3)→(4)→(5)→(3) ← 相遇在环起点3

龟兔赛跑算法因其优雅的数学原理和高效性，成为处理环形链表的经典算法。