# 445 Add Two Numbers II

You are given two **non-empty** linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

**Follow up:**\
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

**Example:**

```
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
```

**The Idea:** Reverse both lists. Then set them to be equal in size by appending 0s to the smaller list. Then sum both lists element by element by using a carry. Create this list along the way. Finally, append the carry at the end assuming it is not zero.

**Complexity:** O(N) time and space, both of which have heavy constants (would not recommend this implementation).

```cpp
pair<int, ListNode*> reverse_list(ListNode *&l) {
    ListNode *iter_front = l, *iter_back = l, *prev_back = nullptr;
    stack<ListNode*> s_rev;

    int size = 0;
    while (iter_back) {
        s_rev.push(iter_back);
        prev_back = iter_back;
        iter_back = iter_back->next;
        size++;
    }

    int swap_half = s_rev.size() / 2;
    while (swap_half) {
        swap(iter_front->val, s_rev.top()->val);
        --swap_half; s_rev.pop();
        iter_front = iter_front->next;
    }

    return {size, prev_back };
}

void make_same_size(pair<int, ListNode*> size_end1, pair<int, ListNode*> size_end2) {
    int diff = size_end1.first - size_end2.first;

    while (diff > 0) {
        ListNode *node = new ListNode(0);
        size_end2.second->next = node;
        size_end2.second = node;
        --diff;
    }

    while (diff < 0) {
        ListNode *node = new ListNode(0);
        size_end1.second->next = node;
        size_end1.second = node;
        ++diff;
    }

    assert(diff == 0);
}

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    pair<int, ListNode*> l1_s = reverse_list(l1);
    pair<int, ListNode*> l2_s = reverse_list(l2);
    make_same_size(l1_s, l2_s);

    ListNode *head = nullptr;
    ListNode *iter = head;

    int carry = 0;
    while (l1) { // both are equal in size
        int i_s1 = l1->val; l1 = l1->next;
        int i_s2 = l2->val; l2 = l2->next;
        int sum = i_s1 + i_s2 + carry;
        int digit = sum % 10;
        carry = sum / 10;

        if (head) {
            ListNode *node = new ListNode(digit);
            iter->next = node;
            iter = node;
        }
        else {
            head = new ListNode(digit);
            iter = head;
        }
    }

    if (carry) {
        ListNode *node = new ListNode(carry);
        if (head)
            iter->next = node;
        else head = node;
    }

    reverse_list(head);
    return head;
}
```

**Testing**

```cpp
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


int main() {
    ListNode *head1 = new ListNode(7);
    ListNode *iter = head1;
    iter->next = new ListNode(2);
    iter = iter->next;
    iter->next = new ListNode(4);
    iter = iter->next;
    iter->next = new ListNode(3);
    iter = iter->next;

    ListNode *head2 = new ListNode(5);
    iter = head2;

    iter->next = new ListNode(6);
    iter = iter->next;
    iter->next = new ListNode(4);
    iter = iter->next;

    ListNode *r = addTwoNumbers(head1, head2);
}
```

**Simplified Python Implementation:**

Convert to stack. Add the stacks together as you pop. Maintain a carry. Add the remainder of a an unfinished stack. Rebuild the linked list from the answer stack.

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def ll_to_stack(self, ll):
        s = []
        while ll:
            s.append(ll.val)
            ll = ll.next
        return s

    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """

        s1 = self.ll_to_stack(l1)
        s2 = self.ll_to_stack(l2)
        ans = []
        carry = 0

        while s1 and s2:
            sum = s1[-1] + s2[-1] + carry
            s1.pop()
            s2.pop()
            if sum >= 10:
                carry = 1
                digit = sum % 10
                ans.append(digit)
            else:
                carry = 0
                ans.append(sum)

        while s1:
            sum = s1[-1] + carry
            s1.pop()
            if sum >= 10:
                carry = 1
                digit = sum % 10
                ans.append(digit)
            else:
                carry = 0
                ans.append(sum)

        while s2:
            sum = s2[-1] + carry
            s2.pop()
            if sum >= 10:
                carry = 1
                digit = sum % 10
                ans.append(digit)
            else:
                carry = 0
                ans.append(sum)

        if carry:
            ans.append(carry)

        # build ll from stack
        head = None
        iter = head
        prev = head
        if ans:
            head = ListNode(ans[-1])
            iter = head
            prev = head
            ans.pop()

        while ans:
            iter = ListNode(ans[-1])
            prev.next = iter
            prev = iter
            ans.pop()

        return head
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/445-add-two-numbers-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.