java如何确定一个链表有环及入口节点

确定一个链表是否存在环及环的入口节点是链表中常见的问题，Java中可以通过快慢指针和哈希表两种方式来解决。

快慢指针法

快慢指针法的主要思想是，使用两个指针，一个指针每次移动两个结点，一个指针每次移动一个结点，两个指针同时从链表的头结点出发，如果存在环，则两个指针必定会相遇。然后再用两个指针分别从相遇点和头结点出发，每次移动一个结点，最终两个指针相遇的结点即为环的入口结点。

• Java代码示例1

public ListNode detectCycle(ListNode head) {
    // 快慢指针
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            // 相遇点
            ListNode meet = slow;
            // 重新从头和相遇点出发，同时移动指针
            while (head != meet) {
                head = head.next;
                meet = meet.next;
            }
            // 相遇结点即为环的入口结点
            return meet;
        }
    }
    return null;
}

• Java代码示例2

public ListNode detectCycle(ListNode head) {
    // 哈希表
    Set<ListNode> set = new HashSet<>();
    while (head != null) {
        if (set.contains(head)) {
            return head;
        } else {
            set.add(head);
        }
        head = head.next;
    }
    return null;
}

以上两种方法均可以解决链表中环的问题，但是快慢指针法的时间复杂度为O(n)，空间复杂度为O(1)，而哈希表法的时间复杂度为O(n)，空间复杂度为O(n)。因此，在处理大型数据时，快慢指针法更优。