题解 | #链表中环的入口结点#

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
          if (pHead == null || pHead.next == null) {
            return null;
        }
         ListNode slow = pHead;
        ListNode fast = pHead;
         // Check if there is a cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
             if (slow == fast) {
                break;
            }
        }
         // If no cycle exists
        if (fast == null || fast.next == null) {
            return null;
        }
         // Move slow pointer to the head and keep fast pointer at the meeting point
        slow = pHead;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
         return slow; // Return the entrance node of the cycle
    }
}

在链表中找到循环入口节点的解决方案包括使用Floyd的乌龟和兔子算法，也称为“慢速和快速指针”方法。

以下是循序渐进的方法：

1.初始化指向链表头的慢速和快速两个指针。

2.将慢速指针每次移动一步，将快速指针每次移动两步。

3.如果链表中有一个循环，那么慢速指针和快速指针最终会在循环中的某个点相遇。

4.将慢速指针重置为链接列表的头部。

5.将慢速和快速指针一步一步地移动，直到它们再次相遇。它们相遇的点将成为循环的入口节点。

该算法有效的原因是，当慢速指针和快速指针相遇时，慢速指针所行进的距离正好是快速指针所行进距离的一半。这可以用数学来证明。通过将慢速指针重置为头部，并以相同的速度移动两个指针，它们将在循环的入口节点相遇。

该算法具有O（n）的时间复杂度和O（1）的空间复杂度，因为它只使用两个指针来遍历链表。