题目
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
思路
思路比较明确，因为是逆序的，我们只要从第一位一直加下去就可以。每次加一位注意结果有没有大于10，大于就在下一位的计算时结果值+1。
考虑最后可能会进一位的情况(即99+1=100)，需要在最后判断进位是否为1，为1则再追加node。
代码
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(-1);
ListNode cur = head;
int carry = 0;
// 循环，直到两个链表都到了末尾
while (l1 != null || l2 != null) {
// 如果为null，则赋值0
// 因为有可能存在l1为空但l2不为空
int d1 = l1 == null ? 0 : l1.val;
int d2 = l2 == null ? 0 : l2.val;
// 计算总和，如果总和大于10，将进位置为1
int sum = d1 + d2 + carry;
carry = sum >= 10 ? 1 : 0;
// 将sum赋值给cur.next，并向前走一步
cur.next = new ListNode(sum % 10);
cur = cur.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
System.out.println(cur.toString());
}
// 如果两个循环结束了而进位为1，则增加一位
if (carry > 0) {
cur.next = new ListNode(1);
}
// 返回开始的节点
return head.next;
}
时间复杂度
我们这里只走一次循环，时间复杂度为 O(n)。
leetcode最终执行时间为10ms，超过84.12%的人。
