@@ -0,0 +1,2377 @@
+package AddTwoNumbersII;%0A%0A/**%0A * You are given two non-empty linked lists representing two non-negative integers. The most%0A * significant digit comes first and each of their nodes contain a single digit. Add the two numbers%0A * and return it as a linked list.%0A *%0A * You may assume the two numbers do not contain any leading zero, except the number 0 itself.%0A *%0A * Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not%0A * allowed.%0A *%0A * Example:%0A * %3Cpre%3E%0A * Input: (7 -%3E 2 -%3E 4 -%3E 3) + (5 -%3E 6 -%3E 4)%0A * Output: 7 -%3E 8 -%3E 0 -%3E 7%0A * %3C/pre%3E%0A */%0Aclass ListNode %7B%0A    int val;%0A    ListNode next;%0A%0A    ListNode(int x) %7B%0A        val = x;%0A    %7D%0A%7D%0A%0Apublic class Solution %7B%0A%0A    private int lengthOf(ListNode listNode) %7B%0A        int n = 0;%0A        while (listNode != null) %7B%0A            n++;%0A            listNode = listNode.next;%0A        %7D%0A        return n;%0A    %7D%0A%0A    private void addNumber(ListNode l, ListNode r) %7B%0A        while (l != null && r != null) %7B%0A            l.val += r.val;%0A            l = l.next;%0A            r = r.next;%0A        %7D%0A    %7D%0A%0A    private int fixup(ListNode listNode) %7B%0A        if (listNode == null) %7B%0A            return 0;%0A        %7D%0A        if (listNode.next == null) %7B%0A            int n = listNode.val / 10;%0A            listNode.val %25= 10;%0A            return n;%0A        %7D%0A        int n = fixup(listNode.next);%0A        listNode.val += n;%0A        n = listNode.val / 10;%0A        listNode.val %25= 10;%0A        return n;%0A    %7D%0A%0A    private ListNode add(ListNode l, int nl, ListNode s, int ns) %7B%0A        ListNode p = l;%0A        int offset = nl - ns;%0A        while (offset %3E 0) %7B%0A            p = p.next;%0A            offset--;%0A        %7D%0A        addNumber(p, s);%0A        int n = fixup(l);%0A        if (n %3E 0) %7B%0A            ListNode node = new ListNode(n);%0A            node.next = l;%0A            return node;%0A        %7D else %7B%0A            // Remove leading zero%0A            while (l.val == 0 && l.next != null) %7B%0A                l = l.next;%0A            %7D%0A            return l;%0A        %7D%0A    %7D%0A%0A    public ListNode addTwoNumbers(ListNode l1, ListNode l2) %7B%0A        if (l1 == null) return l2;%0A        if (l2 == null) return l1;%0A        int l1n = lengthOf(l1);%0A        int l2n = lengthOf(l2);%0A        if (l1n %3C l2n) %7B%0A            return add(l2, l2n, l1, l1n);%0A        %7D else %7B%0A            return add(l1, l1n, l2, l2n);%0A        %7D%0A    %7D%0A%7D

445. Add Two Numbers II