原題

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.

解題

題意是給定兩個(gè)用鏈表表示的數(shù)，鏈表中的每個(gè)節(jié)點(diǎn)是數(shù)字的一位，第一個(gè)節(jié)點(diǎn)是數(shù)的最高位。求兩個(gè)數(shù)的和。

問題主要在于，要從最后一位開始加法和進(jìn)位的話，無(wú)法獲取前面數(shù)位的引用。

所以可以利用棧的思想對(duì)鏈表進(jìn)行“反向”，然后正常計(jì)算即可。

代碼

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;
    }
};