142. Linked List Cycle II ( Hash / Tortoise & hash Algorithms )

1) using unordered_map

Time Complexity : O(n)

class Solution {
public:
    ListNode *detectCycle(ListNode *ptr) {        
        unordered_map<ListNode*, int> hash;
        while(hash[ptr]==0){
            if(ptr==NULL)
                return NULL;
            hash[ptr]=1;
            ptr = ptr->next;
        }
        return ptr;     
    }
};

2)  using unoredered_set

Time Complexity : O(n)

class Solution {
public:
    ListNode *detectCycle(ListNode *ptr) {        
        unordered_set <ListNode*> hash;
        while(hash.count(ptr)==0){
            if(ptr == NULL)
                return NULL;
            hash.insert(ptr);
            ptr = ptr->next;
            
        }
        return ptr;     
    }
};

3) using set

Time Complexity : O(nlogn)

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> hash;
        int size=0;
        ListNode* ptr=head;
        
        while(ptr!=NULL)
        {
            hash.insert(ptr);
            size++;
            if(hash.size()!=size) // key
                return ptr;
            ptr=ptr->next;
        }
        return NULL;       
    }
};

 

2. Floid's Tortoise & Hare Algorithm

Time Complexity : O(n)

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {        
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(slow==fast){ // cycle found
                fast=head;
                while(slow!=fast){
                    fast=fast->next;
                    slow=slow->next;
                }
                return slow;
            }
        }
        return NULL;
    }
};