Problem

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

Example

Given 7->1->6 + 5->9->2. That is, 617 + 295.

Return 2->1->9. That is 912.

Given 3->1->5 and 5->9->2, return 8->0->8.

Note

先判断有没有l1或l2是null的情况，返回另一个即可。然后从头到尾对l1和l2的每一个非空结点和进位数carry求和。再通过取余和整除10将carry的个位数值赋给新链表node = dummy，十位数值更新到下一位的carry初始值。当l1和l2都遍历完之后，如果carry不为0，就给node再增加一个值为carry的结点，即l1和l2求和的最高位。
最后，返回dummy.next。

Solution

public class Solution {
    public ListNode addLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode dummy = new ListNode(0), node = dummy;
        int carry = 0;
        while (l1 != null || l2 != null) {
            if (l1 != null) {
                carry += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                carry += l2.val;
                l2 = l2.next;
            }
            node.next = new ListNode(carry % 10);
            node = node.next;
            carry /= 10;
        }
        if (carry != 0) node.next = new ListNode(carry);
        return dummy.next;
    }
}