[编程题]链式A+B

最为直接的版本：全都往第二个链表中加
严格的：O(min(a,b))

 public class Plus {
    public ListNode plusAB(ListNode a, ListNode b) {
        ListNode ret = b;
        while (a != null) {
            b.val += a.val;
            if (b.val >= 10) {
                b.val %= 10;
                if (b.next == null)
                    b.next = new ListNode(1);
                else
                    b.next.val++;
            }
            if (b.next == null){
                b.next = a.next;
                break;
            }
            a = a.next;
            b = b.next;

        }
        return ret;
    }
}

递归：相加递归，进位递归
进位的递归增加了复杂度：O(Min(a,b)) ~ O(Min(a,b)) + O(max(a,b))
最差的情况是：个为导致后面全部递增
忽然想到这种方式，贴一下
如果这个数是正序的，用这个就会很好了，稍微改一下就行

public  ListNode plusAB(ListNode a, ListNode b) {
        if (a == null || b == null) return b == null ? a : b;
        b.next = plusAB(a.next, b.next);
        b.val += a.val;
        addUp(b, b.next);
        return b;
    }

    private void addUp(ListNode b, ListNode node) {
        if (b.val >= 10) {
            b.val %= 10;
            if (node == null) 
                b.next = node = new ListNode(1);
            else
                node.val++;
            addUp(node, node.next);
        }
    }
}