Addition in Linked List

Problem Statement

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

Solution


class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {

        if( l1 == NULL )
            return l2;
        if( l2 == NULL )
            return l1;

        int carry = 0;
        ListNode *rider = l1, *prev = NULL;

        while( rider != NULL && l2 != NULL )
        {
            int temp = rider->val + l2->val + carry;

            rider->val = temp%10;
            carry = temp/10;
            prev = rider;

            rider = rider->next;
            l2 = l2->next;
        }
        if( rider == NULL && l2 == NULL )
        {
            if(carry > 0)
                prev->next = new ListNode(carry);
        }
        else if( l2 == NULL )
        {
            while( carry > 0 && rider != NULL)
            {
                int temp = rider->val + carry;
                rider->val = temp%10;
                carry = temp/10;

                prev = rider;
                rider = rider->next;
            }
            if(carry > 0 && rider == NULL)
                prev->next = new ListNode(carry);
        }
        else if( rider == NULL )
        {
            while( l2 != NULL )
            {
                int temp = l2->val + carry;
                prev->next = new ListNode( temp%10 );

                carry = temp/10;
                prev = prev->next;
                l2 = l2->next;
            }
            if( carry > 0)
                prev->next = new ListNode( carry );
        }

        return l1;
    }
};
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