142. 环形链表II

题目：给定一个链表，如果有环，返回链表开始入环的第一个节点；如果无环，返回null。
思路1：哈希表
遍历链表中的每个节点，并将其存储在哈希表中，一旦遇到了之前遍历过的节点，就可判定链表中存在环。

ListNode* detectCycle(ListNode *head){
    unordered_set<ListNode*> visited;
    while(head!=nullptr){
        if(visited.count(head)){
            return head;
        }
        visited.insert(head);
        head = head->next;
    }
    return nullptr;
}

思路2：快慢指针
详细解析看leetcode官方题解吧

ListNode* detectCycle(ListNode *head){
    if(head == nullptr || head->next == nullptr) return nullptr;
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast != nullptr){
        if(fast->next == nullptr) return nullptr;
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
            ListNode* ptr = head;
            while(slow!=ptr){
                slow=slow->next;
                ptr=ptr->next;
            }
            return ptr;
        }
    }
    return nullptr;
}