leetcode 141. 环形链表

哈希

class Solution {
public:
    bool hasCycle(ListNode *head) {
        map<ListNode *,int> mp;
        while(head){
            if(mp[head] == 1){
                return true;
            }
            mp[head] = 1;
            head = head->next; 
        }
        return false;
    }
};

快慢指针

两个指针，一个速度是2一个速度是1，同时出发，如果有环前面的会追上后面的

class Solution {
public:
    bool hasCycle(ListNode *head) {

        ListNode * first = head;
        ListNode * second = head;
        while( first && first->next){
            first = first -> next -> next;
            second = second ->next;
            if(first == second){
                return true;
            }
        }
        return false;
    }
};