/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { // 空处理 if (pHead == nullptr || pHead->next == nullptr) { return nullptr; } // 分别定义快慢指针 ListNode* low = pHead; ListNode* high = pHead; // 循环内部处理退出 while (1) { // 慢指针一次走一步 // 因为慢指针不肯呢比快指针先抵达nullptr故不需要这一个判断 // if (low == nullptr) { // break; // } low = low->next; // 快指针一次走两步 // 为防止崩溃(即访问nullptr)故判断high以及high->next if (high == nullptr || high->next == nullptr) { break; } high = high->next->next; // 若无环则快指针永远比慢指针先到达nullptr // 责low == high只能是成环 if (low == high) { // 成环后将low(或high这里指定low)指向链表头 high留在原地 // 改为每次移动一个节点则再次相遇时节点即为环的入口 low = pHead; while (low != high) { low = low->next; high = high->next; } return low; } } return nullptr; } };