Leetcode解题: Add Two Numbers II (445)

You are given two linked lists representing two non-negative numbers. 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

解法1：Reverse + 两数相加

因为list的头是最高位，我们要相加是从最低位开始加，所以如果能先反转的话比较容易做。分别reverse再求和，最后把结果list再reverse一下就可以了。
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) {
            return l2;
        }   

        if (l2 == NULL) {
            return l1;
        }

        l1 = reverse(l1);
        l2 = reverse(l2);

        // normal algorithm
        ListNode* dummy = new ListNode(0);
        ListNode* tail = dummy;

        int carry = 0;
        while (l1 != NULL && l2 != NULL) {
            int temp = l1->val + l2->val + carry;
            int digit = temp % 10;
            carry = temp / 10;
            ListNode* node = new ListNode(digit);
            tail->next = node;
            tail = tail->next;
            l1 = l1->next;
            l2 = l2->next;
        }

        while (l1 != NULL) {
            int temp = l1->val + carry;
            ListNode* node = new ListNode(temp % 10);
            carry = temp / 10;
            tail->next = node;
            tail = tail->next;
            l1 = l1->next;
        }

        while (l2 != NULL) {
            int temp = l2->val + carry;
            ListNode* node = new ListNode(temp % 10);
            carry = temp / 10;
            tail->next = node;
            tail = tail->next;
            l2 = l2->next;
        }

        if (carry != 0) {
            ListNode* node = new ListNode(carry);
            tail->next = node;
            tail = tail->next;
        }

        // reverse back
        ListNode* res = reverse(dummy->next);
        delete dummy;
        return res;
    }

    ListNode* reverse(ListNode* head) {
        ListNode* prev = NULL;
        while (head != NULL) {
            ListNode* temp = head->next;
            head->next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
};

Java

解法2： Follow up O(N) Time and Space

从list的最后加，如果不能反转，需要想到有一种数据结构是可以从后往前存储的，那就是stack。
用两个stack保存每一个队列的node，然后往回加。
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        stack<ListNode*> left;
        stack<ListNode*> right;

        while (l1 != NULL) {
            left.push(l1);
            l1 = l1->next;
        }

        while (l2 != NULL) {
            right.push(l2);
            l2 = l2->next;
        }
        int carry = 0;

        ListNode* res = NULL;
        while (!left.empty() && !right.empty()) {
            ListNode* leftnode = left.top();
            ListNode* rightnode = right.top();
            int temp = leftnode->val + rightnode->val + carry;
            int digit = temp % 10;
            carry = temp / 10;
            ListNode* node = new ListNode(digit);
            node->next = res;
            res = node;
            left.pop();
            right.pop();
        }

        while (!left.empty()) {
            ListNode* leftnode = left.top();
            int temp = leftnode->val + carry;
            int digit = temp % 10;
            carry = temp / 10;
            ListNode* node = new ListNode(digit);
            node->next = res;
            res = node;
            left.pop();
        }

        while (!right.empty()) {
            ListNode* rightnode = right.top();
            int temp = rightnode->val + carry;
            int digit = temp % 10;
            carry = temp / 10;
            ListNode* node = new ListNode(digit);
            node->next = res;
            res = node;
            right.pop();
        }

        if (carry != 0) {
            ListNode* node = new ListNode(carry);
            node->next = res;
            res = node;
        }

        return res;
    }
};