检测链表中的环并找到入口节点

问题定义

给定一个链表，检查链表是否包含环，如果包含，需找到环的入口节点；如果不包含环，则返回null。

解决方案

方案一：利用哈希集合

通过遍历链表的每个节点，并使用哈希集合来记录已访问过的节点。如果遇到一个已经存在于集合中的节点，说明这个节点就是环的入口。如果遍历完整个链表都没有发现重复的节点，则表明链表中没有环。

时间复杂度：O(n)，其中 n 是链表中节点的数量。因为每个节点只会被访问一次。
空间复杂度：O(n)，需要额外的空间来存储已经访问过的节点。

public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set visited = new HashSet<>();
        ListNode node = head;
        while (node != null) {
            if (visited.contains(node)) {
                return node;
            }
            visited.add(node);
            node = node.next;
        }
        return null;
    }
}

方案二：双指针技术（快慢指针）

采用两个指针，快指针（fast）每次移动两步，慢指针（slow）每次移动一步。如果链表中有环，快指针终将会追上慢指针，即两者将在环内某一点相遇。一旦发现相遇点，可以再从链表头开始，以相同的速度移动一个新的指针和慢指针，直到两者再次相遇，该点即为环的入口。

原理在于，从头节点到环入口的距离等于从相遇点到环入口的距离加上若干圈环的长度，这使得从头节点和相遇点同时出发的两个指针能够同步到达环的入口。

public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    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; // 无环
    }
}