上通信的课就跟室友一起刷题玩，结果读题目读了半天，好歹我也是过了四级的人啊，怎么能这样，干脆百度题目意思……

题目：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合并为一个之外，有知道的宝宝么？