LeetCode 445 Add Two Numbers II leetcode

LeetCode 445 Add Two Numbers II

Problem Description：
对给出的两条非空链表结点值按照从尾到头的顺序进行相加
具体的题目信息：
https://leetcode.com/problems/add-two-numbers-ii/description/
【LeetCode 445 Add Two Numbers II】Solution:
- 解题思路：从头开始遍历链表，分别用两个栈存储两条链表各个节点的值，然后对栈顶元素进行相加操作。判断相加之后的和是否大于9，如果是需要将flag值设为1。当对栈顶元素进行相加操作时，需要考虑此时的flag值大小，即上一位是否有进位。每次的计算结果push进结果栈，最后根据结果栈中的值构造链表即可。
- 编程实现：

/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { stack stack1; stack stack2; stack sum; int flag = 0, num = 0; ListNode* p = l1; //分别将两个链表中的值push进相应的栈中 while(p) { stack1.push(p->val); p = p->next; } p = l2; while(p) { stack2.push(p->val); p = p->next; } //对两个栈的栈顶元素进行相加操作 while(!stack1.empty() && !stack2.empty()) { if (flag == 1) { num = stack1.top()+stack2.top()+1; sum.push(num%10); if (num <= 9) flag = 0; } else { num = stack1.top()+stack2.top(); sum.push(num%10); if (num > 9) flag = 1; } stack1.pop(); stack2.pop(); } //对两个栈中尚未为空的栈进行操作 if (stack1.empty()) sum = addStack(stack2, flag, sum); else sum = addStack(stack1, flag, sum); //根据结果栈中的元素构造链表 ListNode *temp = new ListNode(sum.top()); l1 = temp; sum.pop(); temp->next = NULL; ListNode* q; while(!sum.empty()) { q = new ListNode(sum.top()); sum.pop(); q->next = temp->next; temp->next = q; temp = q; } return l1; } //传入三个参数：尚未为空的存储其中一条链表的栈，指示是否有进位的标记值，结果栈 stack addStack(stack temp, int flag, stacksum) { int num; while(!temp.empty()) { if (flag == 1) { num = temp.top()+1; sum.push(num%10); if (num <= 9) flag = 0; } else { num = temp.top(); sum.push(temp.top()); if (num > 9) flag = 1; } temp.pop(); } //若操作之后flag值仍为1说明最后一步结果还需要进行进位 if (flag == 1) sum.push(1); return sum; } };