/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ // 双指针 class Solution { public: bool hasCycle(ListNode *head) { // 空处理 if (head == nullptr || head->next == nullptr) { return false; } // 分别定义快慢指针 ListNode* low = head; ListNode* high = head; // 循环内部处理退出 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) { return true; } } return false; } };