Add Two Numbers

Problem: Add Two Numbers

It's good for us that numbers are in reverse order in list. We can do adding from the first digit to the last and do carry-over if necessary.

Code in Python:

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        ans = ListNode(0)
        cur, x = ans, 0
        while True:
            if not l1 and not l2:
                if x:
                    newNode = ListNode(x)
                    cur.next = newNode
                break
            elif not l1:
                newNode = ListNode((l2.val + x) % 10)
                x = (l2.val + x) / 10
                l2 = l2.next
            elif not l2:
                newNode = ListNode((l1.val + x) % 10)
                x = (l1.val + x) / 10
                l1 = l1.next
            else:
                newNode = ListNode((l1.val + l2.val + x) % 10)
                x = (l1.val + l2.val + x) / 10
                l1, l2 = l1.next, l2.next
            cur.next = newNode
            cur = cur.next
        return ans.next

Code in Java:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode ans = new ListNode(0);
        ListNode prev = ans;
        int carry = 0;
        while (l1 != null && l2 != null) {
            int sum = l1.val + l2.val + carry;
            carry = sum / 10;
            ListNode tmp = new ListNode(sum % 10);
            prev.next = tmp; prev = prev.next;
            l1 = l1.next; l2 = l2.next;
        }
        if (l1 != null) prev.next = addTwoNumbers(l1, new ListNode(carry));
        else if (l2 != null) prev.next = addTwoNumbers(l2, new ListNode(carry));
        else if (carry == 1) prev.next = new ListNode(1);
        return ans.next;
    }
}