一、题目
给出两个非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字， 我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。【力扣链接】
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
二、示例
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
三、分析
这是一道链表题，考验解题者对于链表的操作。 本题是将两个链表变成两个数，进行相加得到他们的和，然后变成链表进行返回。我们可以按照这个方式去做但是所需要的成本有点搞，需要将两个链表都遍历得到数字进行相加，相加完成后，还要进行将数字变成链表返回。这其中对于空间以及时间都有点浪费。
因此我们在重新观察一下本题给的示例，我们不难发现，将两个链表的头节点相加可以得到输出的头节点。将链表的第二个节点相加进行以10取模得到的是输出的第二个节点的。链表的第三个节点相加并加1得到输出的第三个节点。
第二个节点为什么是取模得到第二个节点，因为第二个节点相加大于等于10，因此需要进位，进位后剩下的就是对应的输出节点。
第三个节点为什么相加后进行加一，由于前一个节点大于10进行进位，因此需要加上1完成整体的相加。
但是这样就可以了吗？不是的，假如最后一位相加并加一大于等于10呢，我们是不是就需要将进的一位也要放入链表的最后，这样才是完整的相加。
四、实现
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 返回
ListNode r1 = l1;
// 代表进位标记
int temp = 0;
while (l1 != null || l2 != null) {
// 将链表相同的节点的数值进行相加，并加上进位的值
int num = l1.val + l2.val + temp;
// 判断相加后的值是否大于10，如果大于10需要进位并且以10取模
if (num >= 10) {
temp = 1;
// 取模操作，这样好理解些，也可以直接减10 提升效率
num %= 10;
} else {
temp = 0;
}
// 这里将l1链作为返回的链，因此将值直接赋值，不需要新创建节点，减少空间
l1.val = num;
if (l1.next == null) {
// 由于l1已经结束，l2可能未结束，因此需要进行将l2链后面的进行给l1，使l1变成长链。
l1.next = l2.next;
// 将l2 后面的引用清空。
l2.next = null;
// 判断是否有进位
if (temp == 0) {
break;
}
// 可能l2 也是结束的，这个时候还存在进位，需要新加一个节点，承载进位，并返回
if (l1.next == null) {
l1.next = new ListNode(1);
break;
}
}
l1 = l1.next;
// l2 如果为空并且没有进位了，就可以返回了，否则让l2的数值为0，继续相加。
if (l2.next == null) {
if (temp == 0) {
break;
}
l2.val = 0;
} else {
l2 = l2.next;
}
}
return r1;
}
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
}
其中需要注意的点已经在代码的注视中标出了，总体的思路和小学学习的加法运算一样的，因此大家可以拿出纸笔画下，感觉这个题还是很有意思的题。不建议将链表转成数值，因为可能会存在数组的越界。
五、延伸
/**
* 输入: 1, 2, 3
* 输出: 3->2->1
*/
public static ListNode buildLinkedDesc(int[] is) {
ListNode result = null;
for (int i : is) {
if (result == null) {
result = new ListNode(i);
} else {
ListNode temp = new ListNode(i);
temp.next = result;
result = temp;
}
}
return result;
}
/**
* 输入: 1, 2, 3
* 输出: 1->2->3
*/
public static ListNode buildLinkedAsc(int[] is) {
ListNode result = null;
ListNode current = null;
for (int i : is) {
if (result == null) {
result = new ListNode(i);
current = result;
} else {
current.next = new ListNode(i);
current = current.next;
}
}
return result;
}
可以使用上面的两个方法进行构造出题目中的链表。一个是数组反向的链表，一个是数组正向的列表，其中使用的思路是一个是将数据不断的插入头节点，另一个是不断的插入尾节点。
/**
* 链表反转
* 输入: 1->2->3
* 输出: 3->2->1
*/
public static ListNode reverseListNode(ListNode listNode) {
ListNode temp = listNode.next;
ListNode result = listNode;
result.next = null;
while (temp != null) {
ListNode temp1 = temp.next;
temp.next = result;
result = temp;
temp = temp1;
}
return result;
}
上面的方法是链表反转, 思路是将头节点作为尾节点，然后不断的将剩余的节点作为头节点插入。
/**
* 两个链表相加
* 输入 （1->2->3）+ (4->5->->6)
* 输出 1->2->3->4->5->->6
*/
public static ListNode addListNode(ListNode listNode1,
ListNode listNode2) {
ListNode current = listNode1;
while (current != null) {
if (current.next == null) {
current.next = listNode2;
break;
}
current = current.next;
}
return listNode1;
}
上面的方法是两个链表相加。思路比较简单，不在赘述。
