带环单链表的故事
@不了解前尘往事的Reader，烦请阅读——《判断单链表是否有环的算法》
如何找带环单链表的环的入口
这里只说比较可行的算法吧。
思路一：HashSet第一个重复元素就是环的入口
按照查找单链表带环的思路二，我们用一个HashSet维护已经跑过的元素，当重复的时候，那个结点就是环的入口。这法子还算好使，不过还是老问题——空间复杂度大。
思路二：再开一个指针与当前指针相会
我们当前双指针停在交汇处，这里有一个位置。
思来想去我还是给大家画个图吧：
有两个画错的地方：就是其实l1应该由node4画到node7，再就是node6上的线应该把焦点改到node7。
大家也读过上面的文
在计算机科学中，单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的引用。当这个链表中存在一个循环，即最后一个节点或某节点的引用指向链表中的早先节点，就形成了一个带环单链表。查找带环单链表的环入口是解决这类问题的关键。
我们可以使用两种主要的算法思路来找到环的入口：
1. **HashSet方法**：在这个方法中，我们利用哈希集合（HashSet）存储遍历过程中遇到的每个节点。当遍历到已存在的节点时，该节点就是环的入口。这种方法简单易懂，但缺点是空间复杂度高，因为它需要存储所有已访问的节点。
2. **双指针法**：这种方法更高效，也更节省空间。我们设置两个指针，一个慢指针每次移动一个节点，一个快指针每次移动两个节点。如果链表中存在环，快指针最终会追上慢指针，相遇点即为环内的一个点。为了找到环的入口，我们需要进行如下步骤：
- 初始化两个指针，慢指针和快指针都位于链表头部。
- 遍历链表，直到快指针追上慢指针（即两者相遇）。
- 当快指针追上慢指针后，我们将快指针回退到链表头，慢指针保持在相遇点。
- 再次同时移动慢指针和快指针，每次移动一个节点，它们将在环的入口点相遇。
假设链表的结构如下：
node1 → node2 → node3 → node4 → node5 → node6 → node7 → node8 → node9 → node4
其中，环的入口在node4。按照双指针法的逻辑，我们有以下关键点：
- 慢指针(s)从node1开始，快指针(rear)同样从node1开始。
- 在某时刻，快指针(rear)会在node7追上慢指针(s)。
- 定义变量：l0（从node1到node4的距离），l1（从node4到node7的距离），l2（从node7到node4的距离），r（环的长度，等于l1 + l2）。
- 我们可以建立如下的数学关系：
- s = l0 + l1
- 2s = l0 + l1 + nr（快指针在环内跑了n圈）
- 解得：s = nr
- 结合s = l0 + l1 和 s = nr，我们得到 l0 = (n-1)r + l2
利用这个关系，我们可以创建一个新的指针(new)从node1出发，并让新指针(new)和慢指针(s)同时开始移动，每次移动一个节点。这两个指针最终会在环的入口node4相遇，此时相遇点就是环的入口。
在Java中，我们可以将这个算法实现如下：
```java
public class Main {
private static class Node<T> {
T element;
Node<T> next;
Node(T element) {
this.element = element;
}
}
// 判断链表是否为环
private Node<T> isCircular() {
Node<T> prev = first;
Node<T> rear = first;
while (prev.next != null) {
prev = prev.next;
if (prev.next == null) {
return null;
}
prev = prev.next;
rear = rear.next;
if (prev == rear) {
return prev;
}
}
return null;
}
// 获取环的入口
private Node<T> getEntry() {
Node<T> prev = isCircular();
if (prev == null) {
return null;
}
Node<T> rear = first;
while (prev != rear) {
prev = prev.next;
rear = rear.next;
}
return prev;
}
}
```
以上代码定义了一个`Node`类用于表示链表节点，`isCircular()`方法用于判断链表是否有环，而`getEntry()`方法则用于找到环的入口。通过这些方法，我们可以有效地处理带环单链表并找出环的入口。这种方法既节省空间又具有较高的效率，是解决此类问题的典型策略。
