Add Two Numbers

• LintCode: No.167-Add Binary
• 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.
  

• Analysis:

  Declared a new Linked List to store the sum and scan two Linked Lists to do addition.
  

• Java:

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

• Time Complexity:

  • O(Max(l1.length, l2.length))