LeetCode2

用链表表示整数，求其相加得到的结果。
考察基本的链表操作。
因为用的是Java刷题，所以要清楚Java的链表实现。
Java用引用实现链表，其实引用和指针有很多相似的地方，只不过引用更加安全。

思路

模仿数电中的全加器设计，一个数位的计算包括：
上一位进位，本位对应的两条链表节点的数值
记录下本位的加和结果，向下一位传进位值

c1 = (p1.val + p2.val + c0) / 10;
s = (p1.val + p2.val + c0) % 10;

边界情况分析

这些边界情况有时无法全部想到，只有敲代码的时候才能全面。但是大家编程之前还是要好好考虑一下，不然代码调试起来非常花时间。

• 一条链表为空
  直接返回另外一条链表

• 一条链表到达了末尾，另外一条没有
  加一个判断，未到末尾的继续遍历，不过只用一条链表节点的数值加低位进位了

• 退出循环了但是还有进位
  在末尾添加一个节点

复杂度分析

一趟遍历就可以了，所以复杂度由较长的链表决定
为O（max(m , n))

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode p1 = l1, p2 = l2;
        if(p1 == null){
            return p2;
        }
        if(p2 == null){
            return p1;
        }
        ListNode result = new ListNode(0), p3 = result;
        int c0 = 0 , c1 = 0, s = 0;
        while (p1 != null || p2 != null) {
            if(p1 != null && p2 != null) {
                c1 = (p1.val + p2.val + c0) / 10;
                s = (p1.val + p2.val + c0) % 10;
                p1 = p1.next;
                p2 = p2.next;
            }else{
                ListNode node;
                if(p1 != null){
                    node = p1;
                    p1 = p1.next;
                }else {
                    node = p2;
                    p2 = p2.next;
                }
                c1 = (node.val + c0) / 10;
                s = (node.val + c0) % 10;
            }
            c0 = c1;
            p3.next = new ListNode(s);
            p3 = p3.next;
        }
        if(c0 != 0){
            p3.next = new ListNode(c0);
        }
        return result.next;
    }