Add up two linked list representations of numbers

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8

My initial thoughts:
Add up numbers nodes by nodes. Take care of carries. In each summation of two digits:
sum digit = (digit1 + digit2 + carry_from_previous) % 10;
carry = (digit1 + digit2 + carry_from_previous) – 10;
There are generally three cases needed to be handled:

  • digit1 and digit2 are neigher null
  • digit1 is null
  • digit2 is null

My initial codes:

	public static LLNode<Integer> addWithCarry(LLNode<Integer> head1,
			LLNode<Integer> head2, boolean carry) {
		if (head1 == null && head2 == null) {
			LLNode<Integer> node = carry ? new LLNode<Integer>(1) : null;
			return node;
		}
		int number1 = head1 == null ? 0 : head1.getData();
		int number2 = head2 == null ? 0 : head2.getData();
		int sum = carry ? (number1 + number2 + 1) % 10
				: (number1 + number2) % 10;
		boolean carryNext = carry ? number1 + number2 + 1 >= 10
				: (number1 + number2) >= 10;
		LLNode<Integer> node = new LLNode<Integer>(sum);
		if (head1 != null && head2 != null)
			node.setNext(addWithCarry(head1.getNext(), head2.getNext(),
					carryNext));
		else if (head1 == null)
			node.setNext(addWithCarry(null, head2.getNext(), carryNext));
		else
			node.setNext(addWithCarry(head1.getNext(), null, carryNext));
		return node;
	}

Solution

	public static LLNode<Integer> addList(LLNode<Integer> l1,
			LLNode<Integer> l2, int carry) {
		if (l1 == null && l2 == null)
			return null;
		LLNode<Integer> result = new LLNode<Integer>(carry);
		int value = carry;
		if (l1 != null)
			value += l1.getData();
		if (l2 != null)
			value += l2.getData();
		result.setData(value % 10);
		LLNode<Integer> more = addList(l1 == null ? null : l1.getNext(),
				l2 == null ? null : l2.getNext(), value > 10 ? 1 : 1);
		result.setNext(more);
		return result;
	}

Comments:
There are two mistakes in this solution. Highlighted line 4. If l1 and l2 are both null, you still need to consider the carry: 1 + 9->1 = 0->0->1 but this solution will output 0->0. Highlighted line 13: should be:

value >= 10 ? 1 : 0
Advertisements

7 Comments (+add yours?)

  1. Lei
    May 11, 2012 @ 09:08:54

    Hi Runhe,
    Your solution looks correct to me, but I have a question here, why do you use
    recursive way here?

    Reply

    • Runhe Tian
      May 11, 2012 @ 11:50:47

      Hi Lei, recursion seems natural to me. You can definitely use loops. Any recursion method can be rewritten as loops. But that won’t reduce the time complexity and it’s a little bit harder to write for this problem.

      Reply

  2. matthew
    Oct 04, 2012 @ 23:08:08

    your code does not seem to run for me in eclipse.

    Reply

  3. Jack
    Feb 01, 2014 @ 17:08:52

    Line 4 is actually correct. Since it’s a recursive call, the “return null” here simply sets the “next” of the last element in the result list to be “null”, which is correct. I do agree that line 13 is wrong though.

    Reply

  4. kinshuk4
    May 06, 2014 @ 16:41:57

    Liked your solution man, good to see recursive solution. Here is my iterating solution from http://k2code.blogspot.in/2009/12/write-program-to-add-two-long-positive.html:

    node *long_add(mynode *h1, mynode *h2, mynode *h3) //h3 = h2+h1
    {
    node *c, *c1, *c2;
    int sum, carry, digit;

    carry = 0;
    c1 = h1->next;
    c2 = h2->next;

    while(c1 != h1 && c2 != h2)
    {
    sum = c1->value + c2->value + carry;
    digit = sum % 10;
    carry = sum / 10;

    h3 = insertNode(digit, h3);

    c1 = c1->next;
    c2 = c2->next;
    }

    if(c1 != h1)
    {
    c = c1;
    h = h1;
    }
    else
    {
    c = c2;
    h = h2;
    }

    while(c != h)
    {
    sum = c->value + carry;
    digit = sum % 10;
    carry = sum / 10;
    h3 = insertNode(digit, h3);
    c = c->next;
    }

    if(carry==1)
    {
    h3 = insertNode(carry, h3);
    }

    return(h3);
    }

    Reply

  5. Juned
    Jul 26, 2014 @ 16:34:22

    Jack is wrong about line 4. Tian you are correct about missing to consider the carry:
    I guess if you replace line 3 with below it just works fine then

    if (l1 == null && l2 == null && carry ==0)

    Reply

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: