Linked List Cycle II

 Algorithms and approach and Intuitions 

approach 1:

1.find the collision pts (slow and fast)

2.find the entry pts of cycle 

 slow = l1+ l2;

fast = l1+l2+nc; where n  is the no of cycle in linkedlist

fast = 2slow

l1 = nc - l2;

approach 2:

same as linkedList cycle I

Code 

 // //time complexity ~ O(N) and space complexity is O(1);
    ListNode *detectCycle(ListNode *head) {
        if(head==NULL || head->next==NULL){
            return NULL;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* entry = head;
        while(fast->next!=NULL && fast->next->next!=NULL){
            //find the collision point of fast and slow
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                //find the entry point of cycle 
                while(entry!=slow){
                    entry = entry->next;
                    slow = slow->next;
                }
                return entry ;
            }
        }
        return NULL;
    }
    
    // approach 2nd time complexity = O(N)  //tranverse
    // space complexity = O(N); // hashtable 
    // ListNode *detectCycle(ListNode *head) {
    //     ListNode* dummy = head;
    //     std::unordered_set<ListNode*> s;
    //     while(dummy!=NULL){
    //         auto val = s.find(dummy);
    //         if(val!=s.end()){
    //             return *val;
    //         }
    //         dummy = dummy->next;
    //     }
    //     return NULL;
    // }

Comments

Post a Comment

Popular posts from this blog

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()){ ...
Read more

Palindrome Linked List (LeetCode)

 Algorithms and approach and Intuitions approach 1: 1.tranverse the linkedlist and put the elem of linkedlist in empty vector , string , arr  2.if string then reverse the string and put the reversed string in a another string name P  3.compare them if true return true if not then return false use the ternary operator in c++; 4.bool ans = if(s==p)?return true:return fasle; time complexity is O(2N) and space complexity is O(N); approach 2: step1:find the middle of linkedList using tortoise-hare appraoch make two ptr slow and fast  move the slow by 1 and fast by 2 until the fast->next(odd) and fast->next->next(even)  step2:reverse the linkelist using  return the prev to slow->next  step3: move the head and slow=slow->next by 1 until the slow==NULL  then if not equal return false if equal then  get outside of while  loop then write return false; Code   ListNode* reverseList(ListNode* head){       ...
Read more