上通信的课就跟室友一起刷题玩，结果读题目读了半天，好歹我也是过了四级的人啊，怎么能这样，干脆百度题目意思……
题目：You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
样例：Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
翻译：给你两个链表，然后他们的反序是一个数字（正序2也就是个位，4是十位，3是百位，然后计算他们的俩的和，和输出也是反序，并且是一个链表形式
My View
我的想法是把链表表示的数先算出来，然后两者相加得出答案之后转换为链表，由于结果转化为链表的那部分出现了一点问题，最后也没搭理，几天过去了竟然不想再写，直接去solution了
solution
官方给的示意图：
Figure 1. Visualization of the addition of two numbers: 342 + 465 = 807.
Each node contains a single digit and the digits are stored in reverse order.
到这里可能已经很深刻的理解题目的意思了。
首先我们考虑单独相加的方法，从l1和l2的链表头开始，2+5 = 7,4+6 = 10,10的话就会有进位，作为carry（携带）送给高位，也就是3+4+1 = 8；
那么在这里carry只可能是0或者1，这是符合我们数学逻辑的。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//初始化头结点
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
//进入链表循环
while (p != null || q != null) {
//记录每个节点的值
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
//计算实际值（添加carry之后）
int sum = carry + x + y;
//判断有没有进位
carry = sum / 10;
//添加去除carry位的值
curr.next = new ListNode(sum % 10);
//移动节点
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
//如果到循环结束了还余下一个carry = 1，那么就得新建一个高位，
可以参考l1=[9,9] ，l2=[1] 这种情况
if (carry > 0) {
curr.next = new ListNode(carry);
}
//最后返回dummyHead的下一个节点，（因为第一个节点是0,，java很坑吧）
return dummyHead.next;
}
上述算法的时间复杂和空间复杂都是O(max(m,n))，因为只有一层循环，
所以取决于链表最大长度。
正当试着提交这份代码的时候，系统竟然判定超时，不太理解系统给的方法竟然会超时……
然后去淘discuss，发现大部分人的方法是如下的：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//在定义地方和上面的一致
ListNode c1 = l1;
ListNode c2 = l2;
ListNode sentinel = new ListNode(0);
ListNode d = sentinel;
int sum = 0;
//循环也是一样的
while (c1 != null || c2 != null) {
//这里直接用sum来储存carry和node_sum值
sum /= 10;
if (c1 != null) {
sum += c1.val;
c1 = c1.next;
}
if (c2 != null) {
sum += c2.val;
c2 = c2.next;
}
d.next = new ListNode(sum % 10);
d = d.next;
}
//这里其实和方法一一样
if (sum / 10 == 1)
d.next = new ListNode(1);
return sentinel.next;
}
着实看不懂他俩差别在哪，除了carry与sum合并为一个之外，有知道的宝宝么？
