给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
示例2：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]
示例3：
输入：l1 = [0], l2 = [0]
输出：[0]
提示：
- 链表的长度范围为 [1, 100]
- 0 <= node.val <= 9
- 输入数据保证链表代表的数字无前导 0
进阶：如果输入链表不能翻转该如何解决？
法1：
- 头插法对整个链表原地逆转，
- 之后对链表依次相加取余
- 结果使用头插法的形式插入
//原地逆转
void reverseListNode(ListNode*& l1) {ListNode *res = nullptr;ListNode *cur = nullptr;ListNode *nextNode = nullptr;while (l1) {nextNode = l1->next;cur = l1;cur->next = res;res = cur;l1 = nextNode;}l1 = res;
}
ListNode* addTwoNumbers1(ListNode* l1, ListNode* l2) {//原地逆转链表ListNode *res = nullptr;ListNode *cur = nullptr;reverseListNode(l1);reverseListNode(l2);//对链表依次相加取余int jinwei = 0;while (l1||l2){int n1 = l1 ? l1->val : 0;int n2 = l2 ? l2->val : 0;int sum = n1 + n2 + jinwei;jinwei = sum / 10;//使用头插法的形式插入cur = new ListNode(sum % 10);cur->next = res;res = cur;if (l1){l1 = l1->next;}if (l2) {l2 = l2->next;}}if (jinwei > 0) {cur = new ListNode(jinwei);cur->next = res;res = cur;}return res;
}
法2：
- 使用两个栈分别存储两个链表中的数据，
- 依次从两个栈中分别弹出栈顶数据进行相加取余
- 结果使用头插法进行插入
注：两个栈中的其中一个为空，则使用0代替
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *res = nullptr;ListNode *cur = nullptr;stack<int> s1;stack<int> s2;while (l1){s1.push(l1->val);l1 = l1->next;}while (l2) {s2.push(l2->val);l2 = l2->next;}int jinwei = 0;while (s1.size()>0|| s2.size() > 0){int n1 = s1.empty() ? 0 : s1.top();int n2 = s2.empty() ? 0 : s2.top();int sum = n1 + n2 + jinwei;jinwei = sum / 10;//头插法cur = new ListNode(sum % 10);cur->next = res;res = cur;if (s1.size() > 0){s1.pop();}if (s2.size() > 0) {s2.pop();}}if (jinwei > 0) {cur = new ListNode(jinwei);cur->next = res;res = cur;}return res;
}
