LeetCode链表环检测问题深入解析

题目概述：给定一个单链表，确定其中是否包含环结构，如果包含，则需返回环的入口节点；如果不包含，则返回null。

本问题可采用两种主要策略解决，一是借助额外的数据结构来记录遍历过程中的节点信息，二是仅使用原链表的空间资源进行高效检测。

方案一：使用额外数据结构

此方法推荐使用Java中的HashSet，因为其内部基于HashMap实现，能有效提高查找效率。具体操作是在遍历链表的过程中，每遇到一个新的节点就将其加入HashSet中。一旦发现某个节点已被添加过，即可断定该节点即为环的入口。这种方法的时间复杂度和空间复杂度均为O(n)。

/**
 * 单链表节点定义
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        HashSet visitedNodes = new HashSet<>();
        ListNode current = head;
        while (current != null) {
            if (visitedNodes.contains(current)) return current;
            visitedNodes.add(current);
            current = current.next;
        }
        return null;
    }
}

方案二：不使用额外数据结构

该方法涉及双指针技术，其中一个指针（慢指针）每次移动一个节点，另一个指针（快指针）每次移动两个节点。如果链表中存在环，这两个指针最终会在环内某处相遇。假设从链表头部到环起点的距离为x，从环起点到首次相遇点的距离为y，从首次相遇点绕回环起点的距离为z。因此，当快慢指针相遇时，慢指针走了x+y步，而快指针走了x+y+z+y=x+2y+z步。因为快指针的速度是慢指针的两倍，所以有2(x+y)=x+2y+z，简化得x=z。这意味着，当快慢指针第一次相遇后，让任意一个指针回到链表头部，同时保持另一个指针在相遇点不变，然后以相同速度前进，再次相遇的点即为环的起点。

/**
 * 单链表节点定义
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode slow = head, 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;
    }
}