给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 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;
}
