给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回
null。
如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。
下面介绍两种解决方法：快慢指针法（Floyd 判圈算法）和哈希表法。链表节点定义如下：
1public class ListNode {
2 int val;
3 ListNode next;
4 ListNode(int x) {
5 val = x;
6 next = null;
7 }
8}
方法一：快慢指针法
思路
-
检测环是否存在
使用两个指针：慢指针slow每次走一步，快指针fast每次走两步。如果链表有环，则快慢指针必然在环内相遇；如果无环，快指针会遇到null。 -
寻找环的入口
当快慢指针相遇时，让其中一个指针（例如slow）回到链表头，然后两个指针都每次走一步。它们下一次相遇的节点就是环的入口点。证明（简要说明）：
设链表头到环入口的距离为L，环的长度为C，相遇点距离环入口的距离为D。相遇时，快指针走的距离为L + mC + D，慢指针走的距离为L + nC + D，并且快指针走的路程是慢指针的两倍，所以有： $$ 2(L + nC + D) = L + mC + D $$ 化简得到： $$ L + D = (m - 2n) \times C $$也就是说，从头到环入口的距离
L等于从相遇点到环入口沿环走的距离（补全环一圈的剩余距离），因此当两个指针分别从链表头和相遇点出发以相同速度前进时，会在环入口相遇。
实现代码
Java
1public class Solution {
2 public ListNode detectCycle(ListNode head) {
3 if (head == null) {
4 return null;
5 }
6
7 ListNode slow = head;
8 ListNode fast = head;
9 boolean hasCycle = false;
10
11 // 第一阶段：判断是否存在环
12 while (fast != null && fast.next != null) {
13 slow = slow.next; // 慢指针走一步
14 fast = fast.next.next; // 快指针走两步
15
16 if (slow == fast) { // 相遇，说明有环
17 hasCycle = true;
18 break;
19 }
20 }
21
22 if (!hasCycle) {
23 return null; // 无环，直接返回 null
24 }
25
26 // 第二阶段：寻找环的入口
27 slow = head; // 将慢指针移回链表头
28 while (slow != fast) {
29 slow = slow.next;
30 fast = fast.next; // 两指针均一次走一步
31 }
32
33 // 当两指针相遇时，就是环的入口点
34 return slow;
35 }
36}
C++
1class Solution {
2public:
3 ListNode* detectCycle(ListNode* head) {
4 if (head == nullptr) {
5 return nullptr;
6 }
7
8 ListNode* slow = head;
9 ListNode* fast = head;
10 bool hasCycle = false;
11
12 // 第一阶段：判断是否存在环
13 while (fast != nullptr && fast->next != nullptr) {
14 slow = slow->next; // 慢指针走一步
15 fast = fast->next->next; // 快指针走两步
16 if (slow == fast) { // 相遇，说明存在环
17 hasCycle = true;
18 break;
19 }
20 }
21
22 if (!hasCycle) {
23 return nullptr; // 无环，返回 nullptr
24 }
25
26 // 第二阶段：寻找环的入口
27 slow = head; // 慢指针回到链表头
28 while (slow != fast) {
29 slow = slow->next;
30 fast = fast->next; // 两个指针均一次走一步
31 }
32
33 // 此时 slow 和 fast 相遇，指向环的入口节点
34 return slow;
35 }
36};
方法二：哈希表法
思路
利用一个哈希表（或哈希集合）来记录已经遍历过的节点。遍历链表时：
- 如果当前节点已在哈希集合中，则说明该节点是环的入口（第一次重复出现的节点）。
- 如果遍历过程中遇到
null，则说明链表无环。
这种方法虽然简单直观，但需要额外的空间，其空间复杂度为 O(n)。
实现代码
Java
1import java.util.HashSet;
2import java.util.Set;
3
4public class Solution {
5 public ListNode detectCycleWithHashTable(ListNode head) {
6 Set<ListNode> visited = new HashSet<>();
7 ListNode current = head;
8
9 while (current != null) {
10 // 如果当前节点已经存在于集合中，则找到环的入口
11 if (visited.contains(current)) {
12 return current;
13 }
14 visited.add(current);
15 current = current.next;
16 }
17
18 // 如果遍历结束都没有重复节点，则链表无环
19 return null;
20 }
21}
C++
1#include <unordered_set>
2
3class Solution {
4public:
5 ListNode* detectCycleWithHashTable(ListNode* head) {
6 std::unordered_set<ListNode*> visited;
7 ListNode* current = head;
8
9 while (current != nullptr) {
10 // 如果当前节点已经访问过，则找到了环的入口
11 if (visited.find(current) != visited.end()) {
12 return current;
13 }
14 visited.insert(current);
15 current = current->next;
16 }
17
18 // 遍历结束仍未发现重复节点，说明链表无环
19 return nullptr;
20 }
21};
总结
-
快慢指针法：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
- 优点：不需要额外空间，效率高
- 缺点：理解其证明和算法思路需要一定的数学推导
-
哈希表法：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
- 优点：实现简单，直观易懂
- 缺点：需要额外的空间