【LeetCode】445.|【LeetCode】445. 两数相加 II 【LeetCode】445.两数相加II

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
解题思路：
思路1：把两个链表代表的数字先算出来，然后相加，最后用一个新链表表示。
写完之后运行发现，当数据过大时，会超出数据定义范围。
思路2：把两个链表的每一位数据入栈，然后再每位出栈相加，最后得到一个新的链表，需要注意的是进位的处理，特别是最高位的进位需要单独处理。

ListNode* Solution::addTwoNumbers2new(ListNode* l1, ListNode* l2) { stack stackl1; stack stackl2; int sum1 = 0; int sum2 = 0; int sum = 0; unsigned int carryflag = 0; if((l1 == NULL ) && (l2 == NULL)) { return NULL; } /*1.l1的数值入栈*/ while(l1 != NULL) { stackl1.push(l1->val); l1 = l1->next; } /*2.l2的数值入栈*/ while(l2 != NULL) { stackl2.push(l2->val); l2 = l2->next; } /*3.出栈相加*/ ListNode *prenode = NULL; while((stackl1.empty() != true) || (stackl2.empty() != true)) { sum = sum1 = sum2 = 0; if(stackl1.empty() != true) { sum1 = stackl1.top(); stackl1.pop(); } if(stackl2.empty() != true) { sum2 = stackl2.top(); stackl2.pop(); } if(carryflag == 1) { sum = sum1 + sum2 + 1; carryflag = 0; } else { sum = sum1 + sum2; } if(sum / 10 > 0) { carryflag = 1; } ListNode *pnew = new ListNode(sum % 10); pnew->next = prenode; prenode = pnew; } /*4.处理最高位产生的进位*/ if(carryflag == 1) { ListNode *pnew = new ListNode(1); pnew->next = prenode; prenode = pnew; } return prenode; }

【【LeetCode】445.|【LeetCode】445. 两数相加 II】