人森很精彩，所以要把所有事情都記起來=ˇ=

這題會給你一個linked list的節點，然後要你判斷這個linked list是不是循環的

所謂循環就是你如果一直往下一個next去找，就會陷入永遠找不完的窘境

比如說以下這樣：(圖片取自leetcode)

所以如果-4沒有連到2的話，他就不是一個循環的linked list了

另外這個list裡面的數值是可以重複的，所以... 就別往數值的方向來解了

Sol:

這個題目呢，最直觀就是用一個ser之類的容器記錄下出現過的節點，然後每到一個新節點就去看他有沒有出現過

大概可以寫成這樣：

bool hasCycle(ListNode *head) {
        if (head == nullptr)
            return false;
        
        set<ListNode*> NodeSet;
        
        ListNode* cur = head;
        
        while (cur != nullptr)
        {
            if (NodeSet.count(cur) != 0)
                return true;
            
            NodeSet.insert(cur);
            cur = cur->next;
        }
        return false;

}

就這麼結了，很容易吧

不過這題後面有個小註解：

Can you solve it using O(1) (i.e. constant) memory?

...蛤這是要怎麼用，那不就不能用set了嗎

我思來想去都想不出來，後來還是去看答案了XDDD

原來可以用兩個不同速度去尋訪，一個是比較快的，另一個比較慢

如果快的那個有追上慢的那個的話，就表示是有循環的

code大概是這樣：

    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr)
            return false;

        ListNode* slow = head;

        ListNode* fast = head;

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

這樣看起來雖然比較不直觀，不過也是一個好方法

那這題就這樣了~

下次再見=ˇ=