环形链表

1. 问题描述和示例

问题描述

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

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

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

示例

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

3 -> 2 -> 0 -> -4
     ^          |
     |__________|

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

1 -> 2
^    |
|____|

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

1

2. 核心难点分析

主要难点

1. 环的检测：如何高效地检测链表中是否存在环
2. 空间优化：如何在不使用额外空间的情况下解决问题
3. 指针操作：理解快慢指针的移动规律
4. 数学证明：为什么快慢指针一定会相遇

关键要点

• 环形链表意味着某个节点的next指针指向了之前访问过的节点
• 需要区分"访问过的节点"和"重复的值"
• 快慢指针法是最优解，时间O(n)，空间O(1)
• 如果存在环，快指针最终一定会追上慢指针

3. 多种解法对比

解法一：快慢指针法（Floyd判圈算法）

• 思路：使用两个指针，快指针每次走2步，慢指针每次走1步
• 优点：时间O(n)，空间O(1)，最优解
• 缺点：需要理解数学原理

解法二：哈希表法

• 思路：使用HashSet记录访问过的节点
• 优点：思路直观，容易理解
• 缺点：需要O(n)的额外空间

解法三：标记法

• 思路：修改访问过的节点值进行标记
• 优点：空间复杂度O(1)
• 缺点：破坏了原链表结构

4. 详细Java代码实现

链表节点定义

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) {
        // 边界检查：空链表或只有一个节点且无环
        if (head == null || head.next == null) {
            return false;
        }
        
        // 初始化快慢指针
        ListNode slow = head;      // 慢指针，每次走1步
        ListNode fast = head.next; // 快指针，每次走2步
        
        // 当快指针能够继续移动时
        while (fast != null && fast.next != null) {
            // 如果快慢指针相遇，说明有环
            if (slow == fast) {
                return true;
            }
            
            // 移动指针
            slow = slow.next;        // 慢指针走1步
            fast = fast.next.next;   // 快指针走2步
        }
        
        // 快指针到达链表末尾，说明无环
        return false;
    }
}

解法一的另一种写法

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        // 使用do-while循环，确保至少执行一次
        do {
            // 检查快指针是否能继续移动
            if (fast == null || fast.next == null) {
                return false;
            }
            
            slow = slow.next;
            fast = fast.next.next;
            
        } while (slow != fast);
        
        return true;
    }
}

解法二：哈希表法

import java.util.HashSet;
import java.util.Set;

public class Solution {
    /**
     * 使用HashSet记录访问过的节点
     * @param head 链表头节点
     * @return 如果有环返回true，否则返回false
     */
    public boolean hasCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        
        ListNode current = head;
        while (current != null) {
            // 如果当前节点已经访问过，说明有环
            if (visited.contains(current)) {
                return true;
            }
            
            // 记录当前节点为已访问
            visited.add(current);
            current = current.next;
        }
        
        // 遍历完整个链表都没有重复节点，说明无环
        return false;
    }
}

解法三：标记法（修改节点值）

public class Solution {
    /**
     * 通过修改节点值来标记访问过的节点
     * 注意：这种方法会破坏原链表结构
     * @param head 链表头节点
     * @return 如果有环返回true，否则返回false
     */
    public boolean hasCycle(ListNode head) {
        // 使用一个特殊值作为标记
        final int VISITED = Integer.MAX_VALUE;
        
        ListNode current = head;
        while (current != null) {
            // 如果发现已标记的节点，说明有环
            if (current.val == VISITED) {
                return true;
            }
            
            // 标记当前节点为已访问
            current.val = VISITED;
            current = current.next;
        }
        
        return false;
    }
}

5. 测试用例和预期结果

测试用例

public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // 测试用例1：有环的链表 [3,2,0,-4]，pos=1
        ListNode head1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node0 = new ListNode(0);
        ListNode node4 = new ListNode(-4);
        
        head1.next = node2;
        node2.next = node0;
        node0.next = node4;
        node4.next = node2; // 形成环
        
        System.out.println("测试用例1结果: " + solution.hasCycle(head1)); // 预期输出：true
        
        // 测试用例2：有环的链表 [1,2]，pos=0
        ListNode head2 = new ListNode(1);
        ListNode node2_2 = new ListNode(2);
        
        head2.next = node2_2;
        node2_2.next = head2; // 形成环
        
        System.out.println("测试用例2结果: " + solution.hasCycle(head2)); // 预期输出：true
        
        // 测试用例3：无环的链表 [1]
        ListNode head3 = new ListNode(1);
        System.out.println("测试用例3结果: " + solution.hasCycle(head3)); // 预期输出：false
        
        // 测试用例4：无环的链表 [1,2,3,4,5]
        ListNode head4 = new ListNode(1);
        head4.next = new ListNode(2);
        head4.next.next = new ListNode(3);
        head4.next.next.next = new ListNode(4);
        head4.next.next.next.next = new ListNode(5);
        
        System.out.println("测试用例4结果: " + solution.hasCycle(head4)); // 预期输出：false
        
        // 测试用例5：空链表
        System.out.println("测试用例5结果: " + solution.hasCycle(null)); // 预期输出：false
        
        // 测试用例6：自环链表
        ListNode head6 = new ListNode(1);
        head6.next = head6; // 自己指向自己
        
        System.out.println("测试用例6结果: " + solution.hasCycle(head6)); // 预期输出：true
    }
}

6. 边界情况处理

关键边界情况

1. 空链表：head为null
2. 单节点无环：只有一个节点，next为null
3. 单节点有环：只有一个节点，next指向自己
4. 两节点有环：两个节点互相指向
5. 长链表无环：很长的链表但没有环

边界处理技巧

// 快慢指针法的边界处理
if (head == null || head.next == null) {
    return false;
}

// 在循环中检查快指针的有效性
while (fast != null && fast.next != null) {
    // 移动指针前先检查
    if (slow == fast) {
        return true;
    }
    slow = slow.next;
    fast = fast.next.next;
}

7. 相关题目

类似题目

1. 142. 环形链表 II：找到环的入口节点
2. 287. 寻找重复数：使用Floyd判圈算法的变种
3. 202. 快乐数：判断数字变换过程是否有环
4. 457. 环形数组循环：数组中的环检测
5. 876. 链表的中间结点：快慢指针的另一个应用

题目关联

• 都可以使用快慢指针技巧
• 都涉及环或循环的检测
• Floyd判圈算法的不同应用场景
• 快慢指针是解决链表问题的重要技巧

8. 复杂度分析

时间复杂度

• 快慢指针法：O(n)，其中n是链表中的节点数
  • 无环情况：快指针走到末尾，最多走n步
  • 有环情况：快指针最多在环中走一圈就能追上慢指针
• 哈希表法：O(n)，需要遍历链表
• 标记法：O(n)，需要遍历链表

空间复杂度

• 快慢指针法：O(1)，只使用两个指针
• 哈希表法：O(n)，最坏情况下需要存储所有节点
• 标记法：O(1)，不使用额外空间

最优解选择

推荐使用快慢指针法，因为：

• 时间复杂度最优：O(n)
• 空间复杂度最优：O(1)
• 不破坏原链表结构
• 是经典的Floyd判圈算法

9. 面试要点总结

核心考点

1. Floyd判圈算法：快慢指针的经典应用
2. 数学证明：为什么快慢指针一定会相遇
3. 指针操作：正确处理指针的移动和边界
4. 空间优化：如何在O(1)空间内解决问题

面试回答要点

1. 问题分析：这是一个环检测问题
2. 方法选择：推荐快慢指针法，解释优势
3. 算法原理：解释为什么快慢指针会相遇
4. 代码实现：写出清晰的代码
5. 复杂度分析：分析时间和空间复杂度

常见面试问题

• 为什么快慢指针一定会相遇？
• 如何证明算法的正确性？
• 能否找到环的入口位置？
• 还有哪些问题可以用快慢指针解决？

10. 性能优化技巧

Floyd判圈算法的数学原理

设链表头到环入口的距离为a，环的长度为b
当快慢指针相遇时：
- 慢指针走的距离：a + mb（m为慢指针在环中走的圈数）
- 快指针走的距离：a + nb（n为快指针在环中走的圈数）

由于快指针速度是慢指针的2倍：
2(a + mb) = a + nb
化简得：a = (n-2m)b

这证明了如果有环，快慢指针一定会相遇

优化的快慢指针实现

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    
    // 使用短路求值优化判断条件
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        
        // 相遇检查放在移动之后，避免初始状态的误判
        if (slow == fast) {
            return true;
        }
    }
    
    return false;
}

扩展：找到环的入口（环形链表II）

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    
    // 第一阶段：检测是否有环
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow == fast) {
            // 第二阶段：找到环的入口
            ListNode ptr = head;
            while (ptr != slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    
    return null;
}

性能对比

方法	时间复杂度	空间复杂度	代码复杂度	推荐度
快慢指针	O(n)	O(1)	中等	⭐⭐⭐⭐⭐
哈希表	O(n)	O(n)	简单	⭐⭐⭐
标记法	O(n)	O(1)	简单	⭐⭐

总结

环形链表检测是链表问题中的经典题目，核心在于：

1. 理解Floyd判圈算法的原理
2. 掌握快慢指针的使用技巧
3. 正确处理边界情况
4. 理解算法的数学证明

这道题不仅考查链表操作，更重要的是考查对经典算法的理解。快慢指针技巧在很多问题中都有应用，是必须掌握的重要技能。建议深入理解Floyd判圈算法的原理，并练习相关的变种问题。