71 lines
2.0 KiB
C++
71 lines
2.0 KiB
C++
#include "s0142_linked_list_cycle.hpp"
|
|
|
|
IterResult S0142::iter(ListNode *fast, ListNode *slow, bool startUp) {
|
|
// 终止条件
|
|
if (fast == nullptr || slow == nullptr) {
|
|
return {nullptr, false};
|
|
}
|
|
if (fast->next == nullptr) {
|
|
return {nullptr, false};
|
|
}
|
|
if (slow->next == slow) {
|
|
return {slow, true};
|
|
}
|
|
// 当两指针相遇时同样达到终止条件
|
|
if (fast == slow && !startUp) {
|
|
return {nullptr, true};
|
|
}
|
|
// 递归
|
|
IterResult result = iter(fast->next->next, slow->next, false);
|
|
// 从后往前遍历
|
|
// 达到了终止条件，但是没有两个指针遇见过
|
|
// 这说明没有环
|
|
if (!result.meet) {
|
|
return {nullptr, false};
|
|
} else {
|
|
// 有环的情况
|
|
// 我们把 fast 和 fast-next 节点所经过的足迹全部记录下来
|
|
// key 是所经过的节点
|
|
// value 是所经过的次数
|
|
if (footprint.count(fast) == 0) {
|
|
footprint[fast] = 1;
|
|
} else {
|
|
footprint[fast] += 1;
|
|
}
|
|
if (footprint.count(fast->next) == 0) {
|
|
footprint[fast->next] = 1;
|
|
} else {
|
|
footprint[fast->next] += 1;
|
|
}
|
|
// 什么情况下是环的入口呢？
|
|
// 1. footprint[fast] == 1 && footprint[fast->next] > 1
|
|
// 2. footprint[fast->next] == 1 && footprint[fast->next->next] > 1
|
|
if (footprint.count(fast) == 1 && footprint.count(fast->next) == 1) {
|
|
if (footprint[fast] == 1 && footprint[fast->next] > 1) {
|
|
return {fast->next, true};
|
|
}
|
|
}
|
|
if (footprint.count(fast->next) == 1 &&
|
|
footprint.count(fast->next->next) == 1) {
|
|
if (footprint[fast->next] == 1 && footprint[fast->next->next] > 1) {
|
|
return {fast->next->next, true};
|
|
}
|
|
}
|
|
// 返回
|
|
return result;
|
|
}
|
|
}
|
|
|
|
ListNode *S0142::detectCycle(ListNode *head) {
|
|
if (head == nullptr) {
|
|
return nullptr;
|
|
}
|
|
if (head->next == nullptr) {
|
|
return nullptr;
|
|
}
|
|
// 递归函数无法处理所有节点都在环里的情况，所以在这里加一个哑节点
|
|
ListNode dummy = ListNode(0);
|
|
dummy.next = head;
|
|
return iter(&dummy, &dummy, true).node;
|
|
}
|