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).

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

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.

# 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