原题

LintCode 221. Add Two Numbers II

Description

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in forward order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

Example

Given 6->1->7 + 2->9->5. That is, 617 + 295.

Return 9->1->2. That is, 912.

解题

题意是给定两个用链表表示的数，链表中的每个节点是数字的一位，第一个节点是数的最高位。求两个数的和。

问题主要在于，要从最后一位开始加法和进位的话，无法获取前面数位的引用。

所以可以利用栈的思想对链表进行“反向”，然后正常计算即可。

代码

class Solution {
public:
    /*
    * @param l1: The first list.
    * @param l2: The second list.
    * @return: the sum list of l1 and l2.
    */
    ListNode * addLists2(ListNode * l1, ListNode * l2) {
        // write your code here
        ListNode *ans = nullptr;
        stack<int> stack1, stack2;
        while (l1 != nullptr) {
            stack1.push(l1->val);
            l1 = l1->next;
        }
        while (l2 != nullptr) {
            stack2.push(l2->val);
            l2 = l2->next;
        }
        stack<int> &s1 = stack1.size() >= stack2.size() ? stack1 : stack2;
        stack<int> &s2 = stack1.size() >= stack2.size() ? stack2 : stack1;
        while (!s1.empty()) {
            int a, b;
            a = s1.top();
            s1.pop();
            if (s2.size()) {
                b = s2.top();
                s2.pop();
            } else {
                b = 0;
            }
            int sum = a + b;
            int carry = sum / 10;
            ListNode *temp = ans;
            ans = new ListNode(sum % 10);
            ans->next = temp;
            if (carry > 0) {
                if (s1.empty()) {
                    ListNode *temp = ans;
                    ans = new ListNode(carry);
                    ans->next = temp;
                } else {
                    s1.top() += carry;
                }
            }
        }
        return ans;
    }
};