Add Two Numbers

Add Two Numbers

 

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Naive Way: 审题：1.non-negative numbers 2. stored in reverse order 3. linked-list
使用两个指针遍历两个链表。

算法复杂度是O(n)， space O(1)。

/**
 * 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) {
        ListNode head1 = new ListNode(0);
        ListNode head2 = new ListNode(0);
        boolean carry = false;
        head1.next = l1;
        head2.next = l2;
        l1 = head1;
        l2 = head2;
        while(l1.next!=null && l2.next!=null){
            l1 = l1.next;
            l2 = l2.next;
            l1.val += l2.val+(carry?1:0);
            carry = l1.val>9;
            l1.val = l1.val%10;
        }
        while(l2.next!=null){
            l2 = l2.next;
            l2.val += carry?1:0;
            carry = l2.val>9;
            l2.val = l2.val%10;
            l1.next = l2;
            l1 = l1.next;
        }
        while(l1.next!=null){
            l1 = l1.next;
            l1.val+= carry?1:0;
            carry = l1.val >9;
            l1.val = l1.val%10;
        }
        if(carry){
            ListNode tail = new ListNode(1);
            l1.next = tail;
        }
        return head1.next;
    }
}


可以用一个循环完成。还可以把carry也写进去，但是觉得把carry单独写清楚些。

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode pre = head;
        ListNode cur = pre;
        head.next = l1==null?l2:l1;
        boolean carry = false;
        while(l1!=null || l2!=null){
            int val = (l1==null?0:l1.val)+(l2==null?0:l2.val)+(carry?1:0);
            carry = val > 9;
            val %= 10;
            cur = l1==null?l2:l1;
            cur.val = val;
            
            pre.next = cur;
            pre = cur;
            l1 = l1==null?l1:l1.next;
            l2 = l2==null?l2:l2.next;
        }
        if(carry){
            ListNode tail = new ListNode(1);
            pre.next = tail;
        }
        return head.next;
    }
}

还可以是recursive的，但是需要O(n)的space。这里意外的法相虽然recursive的要用O(n)的space，但是用时还是比iterative的少得多。标记一下，看以后的题目是不是这样的。

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        return addTwoNumbers(l1,l2,head,false);
    }
    
    private ListNode addTwoNumbers(ListNode t1, ListNode t2, ListNode pre, boolean carry){
        // base case
        if(t1==null && t2==null)
            return carry?new ListNode(1):null;
        // recursive
        ListNode cur = t1==null?t2:t1;
        cur.val = (t1==null?0:t1.val)+(t2==null?0:t2.val)+(carry?1:0);
        carry = cur.val > 9;
        cur.val %= 10;
        pre.next = cur;
        cur.next = addTwoNumbers(t1==null?t1:t1.next, t2==null?t2:t2.next, cur, carry);
        return cur;
    }
    
}