思路

1. 记录入度和出度，但是需要新的空间
2. 设置一个数组初始化为0，对于已访问的节点变为1，需要新的空间
3. 使用快慢指针，如果有环，两个指针终究会相遇；如果没有，一定是快指针先访问到空

步骤

1. 先判断是否为空链表或者是单节点链表 (head!=nullptr || head->next=nullptr)
2. 设置快指针和慢指针，均指向头节点head；快指针比慢指针多走一步

错误分析

class Solution {
  public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr) return false;

        ListNode* slow = head;
        ListNode* fast = head;
        if (slow->next == nullptr || fast->next->next == nullptr) return false;

        while (slow->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
};

• 第8行：如果前面的判断条件成立会直接返回false，那么就判断不了后面的；只有当 head->next != nullptr 时，才会访问 fast->next->next（即 (head->next)->next），此时 head->next 已确认非空，访问 ->next 安全（即使值为 nullptr 也没问题）。
• 第10行：后面的判断可能会出现段错误。
• 如果链表长度为3，在进行第一次时状态为 head->slow->fast->nullptr（前面的判断语句不会出错），那么该状态下再执行while中的判断语句 fast->next->next == nullptr 时，会出现判断的是 nullptr->next，空指针解引用，导致段错误（SIGSEGV）或 abort（SIGABRT）。

那也就是需要保证快指针可以正常的前进，并且因为一定是快指针先访问到空，所以更改while的条件，并且补充判断单节点的状态

正确答案

/**
 * 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* slow = head;
        ListNode* fast = head;

        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
};