原题：
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
解答：
根据题意，两个非负整数进行相加得到另一个非负整数，只不过用单链表逆序方式存储非负整数的每一位的值，下面是两个数相加图解：
算法：
对于两个非负整数相加，需要考虑以下情况：
- 两个数位数相同，除第一位相加外，不产生进位
- 两个数位数相同，除第一位相加外，产生进位
- 两个数位数不同，除第一位相加外，不产生进位
- 两个数位数不同，除第一位相加外，产生进位
- 两个数第一位相加，产生额外进位
由于在这道题中将数字转为单链表存储，下面以单链表的数据结构进行分析。
那么，如何处理进位的问题呢？
例如6 + 5 = 11， 这时会出现进位，在当前位只需保留1，我们可以用10求余得到结果，即 11 % 10得到当前位的数字1。用remainder保存当前进位的值，将其带入下一次循环中，与其位的数字相加。由于是个位数相加，向后进的位数必然不会超过1，因为9 + 9 + 1 = 19，不会超过20，也就是0和1。
单链表的特性是每一个节点都有一个next属性指向下一个节点，所以我们利用此特性来遍历单链表l1, l2，流程如下：
- 初始化数据
- 循环两个单链表进行计算
- 判断两个单链表的当前节点是否为空并与remainder相加得到res；
- 计算当前需要向后进的位数remainder = res / 10；
- 计算当前位的数值 res = res % 10；
- 判断要返回的单链表是否为null，为空则创建头节点，否则创建节点作为当前节点的下一个节点，然后将当前结点前进到下一个结点；
- 判断两个单链表当前节点是否为null，然后将当前结点前进到下一个结点；
- 在处理最后一位时，可能会产生进位，判断remainder是否大于0，如果大于0，在最后一个节点之后再增加一个结点，值为remainder。
实现代码如下：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = null;
ListNode temp1 = l1;
ListNode temp2 = l2;
ListNode curr = null;
int remainder = 0;
while (temp1 != null || temp2 != null) {
// 这里需要处理链表节点为null的情况
int res = (temp1 != null ? temp1.val : 0) + (temp2 != null ? temp2.val : 0) + remainder;
remainder = 0;
if (res >= 10) {
remainder = res / 10;
}
res = res % 10;
if (result == null) {
// 创建头结点
curr = result = new ListNode(res);
} else {
curr.next = new ListNode(res);
curr = curr.next;
}
if (temp1 != null) {
temp1 = temp1.next;
}
if (temp2 != null) {
temp2 = temp2.next;
}
}
// 处理最后一位相加大于10的情况，由于节点只存储单个数字
// 像 l1: 2 -> 5, l2: 3-> 5, 需要再向后添加一个结点
if (remainder > 0) {
curr.next = new ListNode(remainder);
}
return result;
}
时间复杂度：
设l1的链表长度为m，l2的链表长度为n，遍历次数是m和n的最大值，所以时间复杂度为O(max(m, n))。
空间复杂度：
考虑到最后一位进位情况，生成的链表最大长度为max(m, n) + 1， 所以空间复杂度为O(max(m, n))。
其他解法欢迎补充~