Adding two linked-list representations of 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.
IUNPUT: (2 -> 4 -> 3) + (5 -> 6 -> 4) (i.e. 342 + 465)
OUTPUT: 7 -> 0 -> 8 (i.e. 342 + 465 = 807)

Thoughts:
We just add element by element, as the way we manually do addition. We need to take care of two things:

  1. We should not forge the carry, especially when we have one more digit just for the carry. (e.g., 5 + 7 = 12, the ‘1’ in 12 is due to the carry from last digit)
  2. We should be careful about the fact that these two numbers might not be of the same digits. (e.g., 7 + 3456)

Code (Java):

/**
 * 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) {
        int carry = 0;
        ListNode l3 = null;
        ListNode iter = null;
        while(l1 != null || l2 != null) {
            int v1 = l1 == null ? 0 : l1.val;
            int v2 = l2 == null ? 0 : l2.val;
            int sum = (v1 + v2 + carry) % 10;
            carry = (v1 + v2 + carry) / 10;
            
            ListNode node = new ListNode(sum);
            node.next = null;
            if(l3 == null) {
                iter = node;
                l3 = node;
            } else {
                iter.next = node;
                iter = node;
            }
            
            l1 = l1 == null? null : l1.next;
            l2 = l2 == null? null : l2.next;
        }
        if(carry != 0) {
            ListNode node = new ListNode(carry);
            node.next = null;
            iter.next = node;
            iter = node;
        }
        return l3;
    }
}

Code (C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        int carry = 0;
        ListNode *l3 = NULL;
        ListNode *iter = NULL;
        while(l1 != NULL || l2 != NULL) {
            int v1 = l1 == NULL ? 0 : l1->val;
            int v2 = l2 == NULL ? 0 : l2->val;
            int sum = (v1 + v2 + carry) % 10;
            carry = (v1 + v2 + carry) / 10;
            
            ListNode *node = new ListNode(sum);
            if(l3 == NULL) {
                iter = node;
                l3 = node;
            } else {
                iter->next = node;
                iter = node;
            }
            
            l1 = l1 == NULL? NULL : l1->next;
            l2 = l2 == NULL? NULL : l2->next;
        }
        if(carry != 0) {
            ListNode *node = new ListNode(carry);
            node->next = NULL;
            iter->next = node;
            iter = node;
        }
        return l3;
    }
};
Advertisements

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

%d bloggers like this: