给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
思路：设虚拟头结点，遍历链表求出两个节点的val之和；要注意进位的问题
/**
时间复杂度：O(max(m,n)) 其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1)的时间
空间复杂度：O(1)
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//0.边界处理
if(l1==null) return l2;
if(l2==null) return l1;
//1.定义需要的数据结构
ListNode dummyHead = new ListNode(-1);
ListNode tailNode = dummyHead;
int carry = 0;//进位
//2.遍历得到两数之和
while(l1 !=null || l2 != null) {//只有在两个链表都为空时，退出循环
//获取结点的值
int v1 = (l1==null)?0:l1.val;
int v2 = (l2==null)?0:l2.val;
//计算两数之和 还有进位
int sum = v1 + v2 + carry;
carry = sum/10;
//拼接结点
ListNode node = new ListNode(sum%10);//取余
tailNode.next = node;
tailNode = node;//更新尾结点
//更新
l1 = (l1==null)?l1:l1.next;
l2 = (l2==null)?l2:l2.next;
}
//3.处理最后的进位
if(carry>0) {
tailNode.next = new ListNode(carry);
}
//4.返回结果
return dummyHead.next;
}
}
