Saturday, June 7, 2014

Add Two Numbers

Simple question I believe. Just a few cases we need to be aware of: 1) l1 and l2 are NOT always of the same length; 2) for cases like {1}, {9} we need to add a new digit, or node even l1 and l2 are both null.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        int addOne = 0;
        ListNode newHead = null;
        ListNode tmpNode = null;
        while(l1!=null && l2!=null){
            int sum = l1.val + l2.val + addOne;
            int val = sum%10;
            if(sum > 9) addOne = 1;
            else addOne = 0;
            if(newHead == null){
                newHead = new ListNode(val);
                tmpNode = newHead;
            }
            else{
                ListNode node = new ListNode(val);
                tmpNode.next = node;
                tmpNode = tmpNode.next;
            }
         
            l1 = l1.next;
            l2 = l2.next;
        }
     
        if(l1 == null && l2!=null){
            while(l2!=null){
                int sum = l2.val + addOne;
                int val = sum%10;
                if(sum > 9) addOne = 1;
                else addOne = 0;
                ListNode node = new ListNode(val);
                tmpNode.next = node;
                tmpNode = tmpNode.next;
                l2 = l2.next;
            }
         
        }else{
            if(l1!= null ){
                while(l1!=null){
                    int sum = l1.val + addOne;
                    int val = sum%10;
                    if(sum > 9) addOne = 1;
                    else addOne = 0;
                    ListNode node = new ListNode(val);
                    tmpNode.next = node;
                    tmpNode = tmpNode.next;
                    l1 = l1.next;
                }
            }
        }
        if(addOne == 1) {// inspired by case {1}, {9,9}
            ListNode node = new ListNode(addOne);
            tmpNode.next = node;
            tmpNode = tmpNode.next;                  
        }
        return newHead;
    }
}

No comments:

Post a Comment