题目描述

法一 栈

本题旨在从后往前加，为了逆序处理所有数位，利用栈，把数字压入栈中，再依次取出相加，注意进位！进位是/10，另外需要注意栈的常用函数，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，若是两个链表一样长，且第一位有进位 
			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;    // 进位 
			cur %= 10;         // 余数是当前位的值 
			auto curNode = new ListNode(cur);
			curNode->next = ans;
			ans = curNode;	
		}
		return ans;
	}
};