给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 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
进阶：如果输入链表不能翻转该如何解决？
思路
先将两个输入的链表反转，然后进行逐位相加，最后将结果再反转回来。让最低位在前，在相加过程中可以方便地处理进位问题。最后再将结果反转，使得最高位在前，满足题目要求。
在进行逐位相加的过程中，代码中定义了一个新的链表，用来存储相加的结果。在遍历输入的两个链表的过程中，每次取出两个链表当前节点的值相加，并加上新链表当前节点的值（用于接收上一位的进位），然后将相加的结果对10取余，得到的值赋给新链表的当前节点，将相加的结果除以10得到的值作为进位，如果进位不为0，则在新链表中添加一个新的节点，用于存储这个进位。
在处理完两个链表共有的部分后，如果两个链表的长度不等，还需要将较长的链表剩余的部分也加到新链表中。这部分的处理逻辑和前面相同，只是不再需要加两个链表的节点值，只需要加上新链表当前节点的值（接收上一位的进位）。
最后，将存储结果的新链表反转，并返回。
AC代码
/*
* @lc app=leetcode.cn id=445 lang=cpp
*
* [445] 两数相加 II
*/
// @lc code=start
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
ListNode* l3 = new ListNode();
ListNode* p3 = l3;
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* rl1 = reverse(l1);
ListNode* rl2 = reverse(l2);
ListNode* p1 = rl1;
ListNode* p2 = rl2;
while (p1 != nullptr && p2 != nullptr) {
if (p3->next == nullptr) {
p3->next = new ListNode();
}
p3 = p3->next;
int sum = p1->val + p2->val + p3->val;
int s = sum % 10;
int c = sum / 10;
p3->val = s;
if (c) {
p3->next = new ListNode(c);
}
p1 = p1->next;
p2 = p2->next;
}
move(p1);
move(p2);
l3 = l3->next;
ListNode* rl3 = reverse(l3);
return rl3;
}
ListNode* reverse(ListNode* l) {
ListNode* rl = new ListNode();
ListNode* p = l;
ListNode* rp;
while (p != nullptr) {
rp = new ListNode(p->val);
rp->next = rl->next;
rl->next = rp;
p = p->next;
}
rl = rl->next;
return rl;
}
void move(ListNode* p) {
while (p != nullptr) {
if (p3->next == nullptr) {
p3->next = new ListNode();
}
p3 = p3->next;
int sum = p->val + p3->val;
int s = sum % 10;
int c = sum / 10;
p3->val = s;
if (c) {
p3->next = new ListNode(c);
}
p = p->next;
}
}
};
// @lc code=end
