题目链接
https://leetcode-cn.com/problems/add-two-numbers/
题目描述
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
解题方案
思路
- 使用进位变量carry存放进位值
- 使用一个假头节点dummyHead来链接“结果链表”，详见画解
代码
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode curr = dummyHead;//当前节点与dummyHead共同链接到curr.next
int carry = 0;//用于进位，进位为1，默认为0
while (l1 != null || l2 != null) {//使用||，因为l1和l2可能长度不一致
int x = (l1 == null ? 0 : l1.val);//三元运算符避免l1.val报错
int y = (l2 == null ? 0 : l2.val);
int sum = x + y + carry;//carry为0时，对结果没有影响
carry = sum / 10;//取整，0或1
curr.next = new ListNode(sum % 10);//取余
curr = curr.next;//当前节点变为下一个节点，循环的关键
if (l1 != null)//不能为空，否则l1.next报错
l1 = l1.next;//l1.next可以为空
if (l2 != null)
l2 = l2.next;//l2.next与l1.next均为空时，结束循环，避免无限循环
}
if (carry == 1) {//[5]+[5]->[10]
curr.next = new ListNode(carry);
}
return dummyHead.next;//首节点不要
}
}
画解
1.png
2.png
3.png
4.png
5.png
6.png
7.png
8.png
测试用例
| 输入 | 情况 |
|---|---|
| l1=[0,1]，l2=[0,1,2] | 长度不一致 |
| l1=[]，l2=[0,1] | 一个为空 |
| l1=[9,9]，l2=[1] | 进位 |
