解析

//! n,n ->  每个节点遍历一遍耗时n，hashSet占地n
class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    unordered_set<ListNode *> hashSet;
    ListNode *node = head;
    while (node != nullptr) {
      if (hashSet.find(node) != hashSet.end()) {
        return node;
      }
      hashSet.insert(node);
      node=node->next;
    }
    return nullptr;
  }
};

// n,1 -> 耗时n的倍数，占地常数级
class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr) {
      return nullptr;
    }
    ListNode *slow = head->next;
    ListNode *fast = head->next->next;
    while (slow != fast) {
      slow = slow->next;
      if (fast == nullptr || fast->next == nullptr) {
        return nullptr;
      }
      fast = fast->next->next;
    }
    ListNode *ans = head;
    while (slow != ans) {
      slow = slow->next;
      ans = ans->next;
    }
    return ans;
  }
};