题意

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示两数之和的新链表。

示例

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807

• l1 存储的是 2、4、3，也就是整数 342，逆序嘛；
• l2 存储的是 5、6、4，也就是整数 465，逆序嘛；
• 个位相加为 7（2+5），十位相加为 10（4+6，需要进位），百位相加为 7（3+4），加上进位的 1 就是 8

难度

中等

分析

首先，搞清楚“逆序”是什么。

逆序：从后往前的顺序，比如 123 的逆序是 321。

题目中的示例其实也给出了解释，假如逆序链表 l1 为 [2,4,3]，l2 为 [5,6,4]，那么 l1 代表的数字就是 342，l2 为 456。

对于还没有学过链表的球友来说，可以通过二哥的 Java 进阶之路中的LinkedList来学习一下链表的数据结构，大体上就这样：a->b->c->d

两数相加，如果不需要进位的话，就是把对应位置的数字相加，比如 342 + 456 = 798，非常简单。

难点就在于，进位该如何处理。

回想一下我们小学曾经学过的加法竖式，如下图。

对于每一位上的数字相加，都有可能产生进位，比如 4 + 6 = 10，那么 1 就是进位，我们需要把它加到下一位的和中即可。

假设两个链表相同位置的数字分别是 addX 和 addY，进位是 up，那么它们的和（sum）就是 addX + a...