[LeetCode] 445. Add Two Numbers II

轉自LeetCode

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

<Solution>

這題是 Add Two Number 的衍生題

差別在於，這次 input 是正常的順序，沒有 reverse

因此，先把數值丟進 stack，再用 LIFO 的方式處理就好

要注意一點是，答案的 link list 也要按照正常順序

	class Solution {
	public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
	stack<int> stack_1, stack_2;
	//> put value into stack
	while(l1 != NULL || l2 != NULL) {
	if(l1 != NULL) {
	stack_1.push(l1->val);
	l1 = l1->next;
	}
	if(l2 != NULL) {
	stack_2.push(l2->val);
	l2 = l2->next;
	}
	}
	int sum = 0, carry = 0;
	int num1, num2;
	ListNode *ansList = NULL;
	//> calculate the sum
	while(!stack_1.empty() || !stack_2.empty()) {
	if(stack_1.empty()) {
	num1 = 0;
	}
	else {
	num1 = stack_1.top();
	stack_1.pop();
	}
	if(stack_2.empty()) {
	num2 = 0;
	}
	else {
	num2 = stack_2.top();
	stack_2.pop();
	}
	sum = carry + num1 + num2;
	carry = (sum > 9) ? sum / 10 : 0;
	//> build the link list
	ansList = addToFront(sum % 10, ansList);
	}
	if(carry != 0) {
	ansList = addToFront(1, ansList);
	}
	return ansList;
	}
	ListNode *addToFront(const int &val, ListNode * const head) {
	ListNode *tempNode = new ListNode(val);
	tempNode->next = head;
	return tempNode;
	}
	};

view raw addTwoNumbersII.cpp hosted with ❤ by GitHub