1 题目描述

142. 环形链表 II给定一个链表的头节点 head，要求返回链表开始入环的第一个节点。如果没有环，则返回 null。

2 解题思路

1. 快慢指针法：使用两个指针，一个快指针 fast 每次走两步，一个慢指针 slow 每次走一步。
2. 检测环路：如果链表中存在环，则快指针最终会追上慢指针。当两者相遇时，说明找到了环的一部分。
3. 寻找环入口：一旦快慢指针相遇，保持其中一个指针不动，另一个指针回到头节点，然后两个指针以相同的速度前进，它们的相遇点即为环的入口。

3 Java 代码实现

public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 初始化快慢指针
        ListNode fast = head;
        ListNode slow = head;
        
        // 使用快慢指针检测环
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            
            // 快慢指针相遇，说明有环
            if (fast == slow) {
                // 重新定位一个指针到头节点
                ListNode index1 = fast;
                ListNode index2 = head;
                
                // 移动两个指针直到它们再次相遇
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                
                // 返回相遇点，即环的入口
                return index1;
            }
        }
        
        // 如果没有环，返回 null
        return null;
    }
}

• 时间复杂度: O(n)，其中 n 是链表中的节点数量。
• 空间复杂度: O(1)，除了几个指针变量外，没有使用额外的空间。

4 注意事项

• 快慢指针：使用 fast 和 slow 两个指针，fast 指针每次移动两步，slow 指针每次移动一步。
• 环的检测：如果链表中存在环，fast 和 slow 指针最终会在环内相遇。
• 环入口的确定：一旦 fast 和 slow 指针相遇，从头节点出发一个指针 index2，与 slow 指针以相同的速度移动，最终这两个指针会在环的入口处相遇。
• 返回结果：如果找到环的入口，返回该节点；否则返回 null。