142.环形链表 ||

一、哈希表

我们遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* cur = head;
        unordered_set<ListNode*> set;
        while(cur)
        {
            if(set.find(cur)==set.end())
            {
                set.insert(cur);
                cur = cur->next;
            }
            else
                return cur;
        }
        return NULL;
    }
};

二、快慢指针

 class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        //遍历快慢指针，每次快指针移动两步，慢指针移动一步
        //当快指针为NULL时，返回NULL
        while(fast)
        {
            //因为快指针每次走两步，所以要判断fast的下一节点是否为NULL
            //若为NULL，则会报错，因为无法走两步
            if(fast->next==NULL)
                return NULL;
            slow = slow->next;
            fast = fast->next->next;
            if(fast==slow)
            {
                ListNode* temp = head;
                while(temp!=slow)
                {
                    temp = temp->next;
                    slow =slow->next;
                }
                return temp;
            }
        }
        return NULL;
    }
};