Category: DS & Algo

Node* findFirstNode(Node* head) {
        // your code here
        Node* slow = head, *fast = head;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) {
                slow = head;
                while(slow!=fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return NULL;
    }

// Function to check if the linked list has a loop.
    bool detectLoop(Node* head) {
        // your code here
        Node *slow=head, *fast=head;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) return true;
        }
        return false;
    }

Node *cloneLinkedList(Node *head) {
        // Write your code here
        if(head == NULL) return head;
        Node *cur = head;
        // Step 1: create new node and make a link from first to create map
        while(cur) {
            Node *newNode = new Node(cur->data);
            newNode->next = cur->next;
            cur->next = newNode;
            cur = newNode->next;
        }
        // Step 2: Assign random pointer to head2
        cur = head;
        Node *head2 = cur->next;
        while(cur!=NULL) {
            if(cur->random == NULL) cur->next->random = NULL;
            else cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        //Step 3: Make proper link of head and head2 and return head2
        cur=head;
        while(cur) {
            Node *tmp = cur->next;
            cur->next = tmp->next;
            if(tmp->next) tmp->next = tmp->next->next;
            cur=cur->next;
        }
        return head2;
    }

Node* findFirstNode(Node* head) {
        // your code here
        Node* slow = head, *fast = head;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) {
                slow = head;
                while(slow!=fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return NULL;
    }

class Solution {
  public:
    Node* reverseList(struct Node* head) {
       struct Node* cur = head, *prev = NULL, *next = NULL;
        while(cur != NULL) {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    
    Node* removeZero(struct Node* head) {
        while(head != NULL && head->data == 0)
            head = head->next;
        return head;
    }
    
    Node* addTwoLists(Node* num1, Node* num2) {
        // code here
        num1 = removeZero(num1);
        num2 = removeZero(num2);
        num1 = reverseList(num1);
        num2 = reverseList(num2);
        Node *ret = NULL, *cur=NULL;
        int carry = 0;
        
        while(num1 || num2 || carry != 0) {
            int sum = carry;
            if(num1) {
                sum += num1->data;
                num1 = num1->next;
            }
            if(num2) {
                sum += num2->data;
                num2 = num2->next;
            }
            carry = sum/10;
            Node *tmp = new Node(sum % 10);
            if(ret == NULL) {
                ret = tmp;
                cur = tmp;
            } else {
                cur->next = tmp;
                cur = cur->next;
            }
        }
        return reverseList(ret);
    }
};

vector<int> productExceptSelf(vector<int>& arr) {
        // code here
        vector<int> res(arr.size(), 0);
        int totalProduct = 1;
        int zero = 0, index=-1;
        for(int i=0; i<arr.size(); i++)
        {
            if(arr[i] == 0) zero++, index = i;
            else totalProduct *= arr[i];
        }
        if(zero == 0) {
            for(int i=0; i<arr.size(); i++) {
                res[i] = totalProduct / arr[i];
            }
        } else if(zero == 1) {
            res[index] = totalProduct;
        }
        
        return res;
    }

int maxLen(vector<int> &arr) {
        // Your code here
        int res=0, sum=0;
        unordered_map<int, int> mp;
        
        for(int i=0; i<arr.size(); i++) {
            sum += (arr[i] == 0) ? -1 : 1;
            if(sum == 0) res = max(res, i+1);
            else if(mp.find(sum) != mp.end()) res = max(res, i-mp[sum]);
            else mp[sum] = i;
        }
        
        return res;
    }

int longestSubarray(vector<int>& arr, int k) {
        // code here
        int presum = 0, res=0;
        unordered_map<int, int> mp;
        for(int i=0; i<arr.size(); i++) {
            presum += arr[i];
            if(presum == k)
                res = max(res, i+1);
            else if(mp.find(presum-k) != mp.end())
                res = max(res, i-mp[presum-k]);
            
            if(mp.find(presum) == mp.end())
                mp[presum] = i;
        }
        return res;
    }