題目敘述

題目難度: Easy
題目敘述: 這題給定一個linked list 的 head 要求，判斷這個linked list 當中是否存在 Cycle。

這裡的 Cycle 代表，你能夠透過持續跟隨next指標走訪list，而重複的訪問到曾經訪問過的節點，則代表有Cycle

另外，題目還說明了他們是用一個 pos 變數來去將一個linked list 讓Tail node接到特定index的節點上，這代表這題的cycle 只會從 tail node 往回接，而 pos 變數對我們而言不重要，因為它並不是這題能夠存取到的變數

解法

一開始的想法

我的想法是這題可以透過記錄節點是否有走訪過來判斷是否有 Cycle，因為這題會將Tail node 接回其他node，因此如果有Cycle 必定會有節點重複走訪，且無法抵達 NULL。而儲存方式比較快的應該是用 Hash Table 來去實現。

我的解法- Hash Table

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<ListNode*, int> umap;
    bool hasCycle(ListNode *head){
        struct ListNode *ptr = head;

        while(ptr != NULL){
            if(umap.find(ptr) != umap.end()){
                return true;
            }
            umap[ptr] = ptr->val;
            ptr = ptr->next;
        }
        return false;
    }
};

上面定義了一個 hash table 叫做 umap 他的Key與Value 分別為 <ListNode*, int>，分別儲存節點的位址以及節點值，但其實這題節點值也非必要，主要是靠節點位址來判斷是否重複訪問。

一旦指標 ptr 尚未抵達 tail node 時，就會先將節點位址以及節點值存放到 hash table，接著就移動到下一個節點

1 2	umap[ptr] = ptr->val; ptr = ptr->next;

而一旦每次拜訪節點時，會去檢查這個節點是否存在於Hash table 當中，一旦找到就直接回傳 True

1
2
3

if(umap.find(ptr) != umap.end()){
    return true;
}

我的解法- Vector

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<ListNode*> nodelist;
    bool hasCycle(ListNode *head){
        struct ListNode *ptr = head;

        while(ptr != NULL){
            for(int i=0; i<nodelist.size(); i++){
                if(ptr == nodelist[i]) return true;
            }
                nodelist.push_back(ptr);
                ptr = ptr->next;
            }
            return false;
        }
};

這裡儲存方式使用 vector 但缺點就是在每次檢查時，都會耗費 $O(n)$ 時間，n 為 vector 長度，會隨節點數量增加而提升

其他做法 - Floyd’s Cycle-Finding Algorithm

其實就是 Two-Pointer 做法，只要 快跟慢指標在某個節點相遇，就代表有cycle

/**
 * 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 || !head->next) return false; 
        ListNode *slow = head; 
        ListNode *fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next; 

            if (slow == fast) { 
                return true;
            }
        }
        return false;  
    }
};