给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807复制代码
伪代码如下：
- 将当前结点初始化为返回列表的哑结点。
- 将进位carry初始化为0。
- 将p和q分别初始化为列表l1 和l2 的头部。
- 遍历列表l1 和l2 直至到达它们的尾端。
- 将x 设为结点p 的值。如果p 已经到达l1 的末尾，则将其值设置为0
- 将y 设为结点q 的值。如果q 已经到达l2 的末尾，则将其值设置为0
- 设定sum = x + y + carry。
- 更新进位的值，carry=sum/10。
- 创建一个数值为(sum mod 10)的新结点，并将其设置为当前结点的下一个结点，然后将当前结点前进到下一个结点。
- 同时，将p 和q 前进到下一个结点。
- 检查carry=1 是否成立，如果成立，则向返回列表追加一个含有数字1 的新结点。
- 返回哑结点的下一个结点。
请注意，我们使用哑结点来简化代码。如果没有哑结点，则必须编写额外的条件语句来初始化表头的值。
请特别注意以下情况：
| 测试用例 | 说明 |
|---|---|
| l1=[0,1] l1=[0,1] l2=[0,1,2] l2=[0,1,2] | 当一个列表比另一个列表长时。 |
| l1=[] l1=[] l2=[0,1] l2=[0,1] | 当一个列表为空时，即出现空列表。 |
| l1=[9,9] l1=[9,9] l2=[1] l2=[1] | 求和运算最后可能出现额外的进位，这一点很容易被遗忘 |
复杂度分析
时间复杂度：O(max(m,n))，假设m 和n 分别表示l1 和l2 的长度，上面的算法最多重复max(m,n) 次。
空间复杂度：O(max(m,n))， 新列表的长度最多为max(m,n)+1。
拓展
如果链表中的数字不是按逆序存储的呢？例如：
(3→4→2)+(4→6→5)=8→0→7
这种情况下：
解法一：
我们可以利用栈来保存所有的元素，然后利用栈的后进先出的特点就可以从后往前取数字了，我们首先遍历两个链表，将所有数字分别压入两个栈s1和s2中，我们建立一个值为0的res节点，然后开始循环，如果栈不为空，则将栈顶数字加入sum中，然后将res节点值赋为sum%10，然后新建一个进位节点head，赋值为sum/10，如果没有进位，那么就是0，然后我们head后面连上res，将res指向head，这样循环退出后，我们只要看res的值是否为0，为0返回res->next，不为0则返回res即可，参见代码如下：
class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { stack s1, s2; while (l1) { s1.push(l1->val); l1 = l1->next; } while (l2) { s2.push(l2->val); l2 = l2->next; } int sum = 0; ListNode *res = new ListNode(0); while (!s1.empty() || !s2.empty()) { if (!s1.empty()) {sum += s1.top(); s1.pop();} if (!s2.empty()) {sum += s2.top(); s2.pop();} res->val = sum % 10; ListNode *head = new ListNode(sum / 10); head->next = res; res = head; sum /= 10; } return res->val == 0 ? res->next : res; }};复制代码 解法二：
我们首先统计出两个链表长度，然后根据长度来调用递归函数，需要传一个参数差值，递归函数参数中的l1链表长度长于l2，在递归函数中，我们建立一个节点res，如果差值不为0，节点值为l1的值，如果为0，那么就是l1和l2的和，然后在根据差值分别调用递归函数求出节点post，然后要处理进位，如果post的值大于9，那么对10取余，且res的值自增1，然后把pos连到res后面，返回res，最后回到原函数中，我们仍要处理进位情况，参见代码如下：
class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int n1 = getLength(l1), n2 = getLength(l2); ListNode *head = new ListNode(1); head->next = (n1 > n2) ? helper(l1, l2, n1 - n2) : helper(l2, l1, n2 - n1); if (head->next->val > 9) { head->next->val %= 10; return head; } return head->next; } int getLength(ListNode* head) { int cnt = 0; while (head) { ++cnt; head = head->next; } return cnt; } ListNode* helper(ListNode* l1, ListNode* l2, int diff) { if (!l1) return NULL; ListNode *res = (diff == 0) ? new ListNode(l1->val + l2->val) : new ListNode(l1->val); ListNode *post = (diff == 0) ? helper(l1->next, l2->next, 0) : helper(l1->next, l2, diff - 1); if (post && post->val > 9) { post->val %= 10; ++res->val; } res->next = post; return res; }};复制代码 解法三：
先算出两个链表的长度，我们把其中较长的放在l1，然后我们算出两个链表长度差diff。如果diff大于0，我们用l1的值新建节点，并连在cur节点后(cur节点初始化时指向dummy节点)。并且如果l1的值不等于9，那么right节点也指向这个新建的节点，然后cur和l1都分别后移一位，diff自减1。当diff为0后，我们循环遍历，将此时l1和l2的值加起来放入变量val中，如果val大于9，那么val对10取余，right节点自增1，将right后面节点全赋值为0。在cur节点后新建节点，节点值为更新后的val，如果val的值不等于9，那么right节点也指向这个新建的节点，然后cur，l1和l2都分别后移一位。最后我们看dummy节点值若为1，返回dummy节点，如果是0，则返回dummy的下一个节点。
class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int n1 = getLength(l1), n2 = getLength(l2), diff = abs(n1 - n2); if (n1 < n2) swap(l1, l2); ListNode *dummy = new ListNode(0), *cur = dummy, *right = cur; while (diff > 0) { cur->next = new ListNode(l1->val); if (l1->val != 9) right = cur->next; cur = cur->next; l1 = l1->next; --diff; } while (l1) { int val = l1->val + l2->val; if (val > 9) { val %= 10; ++right->val; while (right->next) { right->next->val = 0; right = right->next; } right = cur; } cur->next = new ListNode(val); if (val != 9) right = cur->next; cur = cur->next; l1 = l1->next; l2 = l2->next; } return (dummy->val == 1) ? dummy : dummy->next; } int getLength(ListNode* head) { int cnt = 0; while (head) { ++cnt; head = head->next; } return cnt; }};复制代码 参考资料：