16. 环形链表：判断链表中是否有环，并找到环的入口。

在链表中判断是否存在环，并找到环的入口节点，是经典的链表题目。我们可以使用著名的**“快慢指针”**（Floyd’s Tortoise and Hare）算法来解决这个问题。

1. 问题描述

• 判断是否有环：给定一个链表，判断该链表是否存在环。如果存在环，则链表中某个节点的 next 指针指向之前的某个节点，从而形成了一个环。
• 找到环的入口：如果链表中存在环，找到环的入口节点，即第一个进入环的节点。

2. 算法思路

步骤 1：使用快慢指针判断链表中是否存在环。

• 设置两个指针：slow 和 fast。slow 每次移动一步，fast 每次移动两步。
• 如果 slow 和 fast 最终相遇，则链表中存在环；否则，如果 fast 或 fast.next 为空，则链表中不存在环。

步骤 2：找到环的入口节点。

• 当快慢指针相遇时，设置一个新的指针 ptr 指向链表的头部，同时让 slow 继续从相遇点移动。然后同时移动 ptr 和 slow，每次移动一步。当它们相遇时，相遇点即为环的入口节点。

3. 代码实现

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class LinkedListCycle {
    
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        // 判断是否有环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) { // 相遇，存在环
                break;
            }
        }

        // 如果没有环，返回 null
        if (fast == null || fast.next == null) {
            return null;
        }

        // 找到环的入口
        ListNode ptr = head;
        while (ptr != slow) {
            ptr = ptr.next;
            slow = slow.next;
        }

        return ptr; // 环的入口节点
    }

    public static void main(String[] args) {
        LinkedListCycle solution = new LinkedListCycle();

        // 构造一个有环的链表
        ListNode head = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);

        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // 创建环，node4 指向 node2

        ListNode cycleNode = solution.detectCycle(head);
        if (cycleNode != null) {
            System.out.println("Cycle detected at node with value: " + cycleNode.val);
        } else {
            System.out.println("No cycle detected.");
        }
    }
}

4. 示例解释

假设链表为 3 -> 2 -> 0 -> -4 -> 2（其中 -4 指向 2，形成环）。

1. 判断是否有环：
   • slow 和 fast 指针同时从 3 开始移动。
   • slow 每次移动一步：3 -> 2 -> 0 -> -4。
   • fast 每次移动两步：3 -> 0 -> 2。
   • 当 slow 和 fast 在节点 2 相遇时，说明链表中存在环。
2. 找到环的入口：
   • slow 和 ptr 同时从相遇点 2 和头节点 3 开始移动。
   • slow 和 ptr 会在节点 2 相遇，说明节点 2 是环的入口节点。

5. 复杂度分析

• 时间复杂度：O(n)，其中 n 是链表中节点的数量。判断是否有环和找到环的入口都需要线性时间。
• 空间复杂度：O(1)，只使用了两个额外的指针，没有使用额外的存储空间。

6. 总结

使用快慢指针的方法可以高效地判断链表中是否存在环，并且在 O(1) 空间复杂度下找到环的入口节点。这种方法简单且实用，是处理链表环问题的经典算法之一。