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

The code is not very pretty, I will try to make it look better when I have time. The idea is simple, use a carry to record the carry of sum of every bit. Notice that when one of the listNode is null, you need to handle them separately. Also if there is a carry at the end of the list, you need to create a new node for it.

/**
 * 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;
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode r = l1; //result
        int carry = 0;
        while(p1.next != null) {
            if (p2.next != null) {
                int temp = (carry + p1.val + p2.val)%10;
                carry = (carry + p1.val + p2.val)/10;
                p1.val = temp;
                p2 = p2.next;
                p1 = p1.next;
            }
            else {
                break;
            }
        }
        //adding the last digit
        int temp = (carry + p1.val + p2.val)%10;
        carry = (carry + p1.val + p2.val)/10;
        p1.val = temp;
        // if p2 is null || p1 is null
        if (p1.next == null && p2.next == null) {
            if (carry == 1) {
                p1.next = new ListNode(1);
            }
            return r;
        }
        if (p1.next == null) {
            p1.next = p2.next;
            do{
                p2 = p2.next;
                temp = (carry + p2.val)%10;
                carry = (carry + p2.val)/10;
                p2.val = temp;
            }while(p2.next != null); 
            
            if (carry == 1)
                p2.next = new ListNode(1);
            return r;
        }
        if (p2.next == null) {
            do {
                p1 = p1.next;
                temp = (carry + p1.val)%10;
                carry = (carry + p1.val)/10;
                p1.val = temp;
            } while(p1.next != null);
            if (carry == 1)
                p1.next = new ListNode(1);
            return r;
        }
        return r;
    }
}

The key point to remember is that when finished for head1 != null && head2 != null, use another while loop to try head1 and head2, and finally carry

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s