Linked List Cycle (Leetcode)

 Algorithms and logic and intuitions 

approach 1:

hashmap(unordered_set) and dummy node point to head of linkedlist

dummy check in hashmap find() if dummy present s.end() not equal 

then dummy insert in hashmap if present then return true or *ptr val 

while(dummy!=NULL) if end then return false or NULL;

 approach 2:

slow ptr and fast ptr head point 

they will meet at certain time later 

while(fast->next !=NULL and fast->next->next !=NULL)

slow-1 and fast -2 

then check if(slow ==fast) return true or cycle present 

if not then while ended means that fast->NULL then return false or no cycle present 

Code

bool hasCycle(ListNode *head) {

        // naive approach

        // unordered_set<ListNode*> s;

        // ListNode* dummy = head;

        // while(dummy!=NULL){

        //     if(s.find(dummy)!=s.end()){

        //         return true;

        //     }

        //     s.insert(dummy);

        //     dummy = dummy->next;

        // }

        // return false;

        // Time complexity is O(N) ;

        // space complexity is O(N);

        

        //best approach

        if(head == NULL || head->next == NULL){

            return false;

        }

        ListNode* slow = head;

        ListNode* fast = head;

        while(fast->next!=NULL && fast->next->next!=NULL){

            slow = slow->next;

            fast = fast->next->next;

            if(slow==fast){

                return true;

            }

            

        }

        return false;

        

        // time complexity = O(N);

        // space complexity = O(1);

    }