LeetCode 142. 环形链表 II｜找环的入口节点（哈希表 + 快慢指针数学推导）

题目

给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

思路 1：哈希表（直观易写）

核心思路

遍历链表，用哈希集合记录每一个节点。第一次遇到已经在集合中的节点，就是环的入口。

代码

class Solution {
public:
ListNode* detectCycle(ListNode* head) {
// 哈希表
if (head == NULL || head->next == NULL) {
return NULL;
}
unordered_set<ListNode*> set; // 创建哈希表
ListNode* p = head;
while (p != NULL) {
// 遍历到的节点已在哈希表中→有环，且当前节点就是环的第一个节点
if (set.find(p) != set.end()) {
return p;
}
// 将当前节点加入哈希表
set.insert(p);
p = p->next;
}
return NULL; // 无环
}
};

复杂度

时间复杂度：O(n)

空间复杂度：O(n)（需要哈希表存储节点）

思路 2：快慢指针 + 数学推导（最优解）

核心思路

这一结论的推导过程大致如下：

1.设头结点A到环的第一个结点B这段链表共有a个结点，从环的第一个结点B到快慢指针相遇的结点C这段链表共有b个结点，环共有c个结点

2.快指针每次移动两下，慢指针每次移动一下，它们同时开始移动，则可以得知：慢指针移动距离*2=快指针移动距离。慢指针移动距离为a+b，快指针移动距离为a+b+k*c，其中k为快指针绕环的圈数，则有2*(a+b)=a+b+k*c，化简得 a=k*c-b

3.由 a=k*c-b可以推得，如果一个指针 r 从头结点A出发，一个指针 p 从快慢指针相遇处C出发，在 p 指针在环上跑了(k-1)圈，由多跑了(c-b)，即总路程为(k*c-b)个结点时，p指针跑到环的第一个结点B处，r指针跑的路程为a，也到了环的第一个结点B处，两指针相遇，由此可得出环的第一个结点地址。

代码（精简版）

class Solution {
public:
ListNode* detectCycle(ListNode* head) {
// 空链表、单节点链表不可能有环
if (head == NULL || head->next == NULL) {
return NULL;
}
// 先判断是否为环——快慢指针法
// 再找环的第一个节点
ListNode* fast = head;
ListNode* slow = head;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
// 相遇→有环
if (fast == slow) {
ListNode* p = head;
while (p != fast) {
p = p->next;
fast = fast->next;
}
// 相遇点→环的第一个节点
return p;
}
}
return NULL;
}
};

代码（分函数写法，逻辑更清晰）

用上求是否为环形链表的函数，并将返回类型改为ListNode*，有环→返回快慢指针相遇点；反之→返回NULL

class Solution {
public:
// 有环→找出快慢指针相遇点；反之→返回NULL
ListNode* hasCycle(ListNode* head) {
// 快慢指针
if (head == NULL || head->next == NULL) {
return NULL;
}
ListNode* fast = head;
ListNode* slow = head;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next; // 一次走两步
slow = slow->next; // 一次走一步
if (fast == slow) {
return fast;
}
}
return NULL;
}
ListNode* detectCycle(ListNode* head) {
// 数学
// 找出快慢指针相遇点
ListNode* meetNode = hasCycle(head);
if (meetNode == NULL) {
return NULL; // 无环
}
ListNode* p = head;// 从头结点出发
ListNode* q = meetNode;// 从相遇点出发
// 最后会在环的第一个节点相遇
while (p != q) {
p = p->next;
q = q->next;
}
return p;
}
};

复杂度

时间复杂度：O(n)

空间复杂度：O(1)（仅用几个指针）

总结