2. Add Two Numbers

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* head)
    {
        ListNode* prev = NULL;
        ListNode* curr = head;
        ListNode* Next = NULL;

        while(curr != NULL)
        {
            Next = curr -> next;
            curr -> next = prev;
            prev = curr;
            curr = Next;
        }

        return prev;
    }

    void insertAtTail(ListNode* &head, ListNode* &tail, int digit)
    {
        ListNode* temp = new ListNode(digit);
        if(head == NULL)
        {
           head = temp;
           tail = temp; 
        }
        else
        {
            tail -> next = temp;
            tail = temp;
        }
    }

    ListNode* add(ListNode* l1, ListNode* l2){
        if(l1 == NULL)
            return l2;
        if(l2 == NULL)
            return l1;
        

        ListNode* ansHead = NULL;
        ListNode* ansTail = NULL;
        int carry = 0, sum = 0, digit = 0;

        while(l1 != NULL || l2 != NULL || carry != 0)
        {
            int val1 = 0;
            if(l1 != NULL)
                val1 = l1 -> val;
            int val2 = 0;
            if(l2 != NULL)
                val2 = l2 -> val;

            
            //find sum
            sum = carry + val1 +val2;

            //find the digit
            digit = sum % 10;

            //create node with digit 
            insertAtTail(ansHead, ansTail, digit);

            //find carry
            carry = sum / 10;
            if(l1 != NULL)
                l1 = l1 -> next;
            if(l2 != NULL)
                l2 = l2 -> next;
        }

        return ansHead;
    }


    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //Step 2. add from left
        ListNode* ans = add(l1, l2);

        return ans;
    }
};