題目描述

法一 棧

本題旨在從后往前加，為了逆序處理所有數(shù)位，利用棧，把數(shù)字壓入棧中，再依次取出相加，注意進(jìn)位！進(jìn)位是/10，另外需要注意棧的常用函數(shù)，push()、pop()、top()，棧判空是 !s.empty()

class Solution {
public:ListNode* addTwoNumbers(ListNode *l1, ListNode*l2){stack<int> s1, s2;while(l1){s1.push(l1->val);l1 = l1->next;}while(l2){s2.push(l2->val);l2 = l2->next;}int carry = 0;ListNode *ans = NULL;while(!s1.empty() || !s2.empty() || carry!=0){   // 注意要有carry，若是兩個(gè)鏈表一樣長，且第一位有進(jìn)位 int a = s1.empty() ? 0 : s1.top();int b = s2.empty() ? 0 : s2.top();if (!s1.empty()) s1.pop();if (!s2.empty()) s2.pop();int cur = a + b + carry;carry = cur/10;    // 進(jìn)位 cur %= 10;         // 余數(shù)是當(dāng)前位的值 auto curNode = new ListNode(cur);curNode->next = ans;ans = curNode;	}return ans;}
};