题解 | #判断链表中是否有环#

/**
 * 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;
    }
};