Posts

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){         //reverse the linkedlist          ListNode* prev = NULL;         ListNode* ne
Post a Comment
Read more

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;                 }                 retur
1 comment
Read more

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;        
Post a Comment
Read more