Author: thecodepathshala

double power(double b, int e) {
        // code here
        int n = abs(e);
        double res = 1.0;
        while(n>0) {
            if(n%2 == 0) {
                b *=b;
                n=n/2;
            } else {
                res *= b;
                n--;
            }
        }
        if(e<0) res = double(1.0)/res;
        return res;
    }

void removeLoop(Node* head) {
        // code here
        Node* slow = head, *fast = head;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) {
                slow = head;
                // check if fast and slow pointer at head node
                if(fast == slow) {
                    while(fast->next != slow)
                        fast = fast->next;
                }
                else {
                   while(slow->next !=fast->next) {
                        slow = slow->next;
                        fast = fast->next;
                    } 
                }
                
                fast->next = NULL;
            }
        }
    }

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);
    }
};