Add Two Numbers

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

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

 

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

 

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

Solution

Before jumping to solve the problem, Give few mins gap and think. How can you approach for the problem...

For the above problem statement, the approach i followed is simple.

Steps:

1. Convert ListNode to String

2. Convert String to Int

3. Add the two integers and convert back to string

4. Loop the characters of a string and add them back to ListNode.

Problem comes with step 3

for the input 

{ 2, 4, 3 } & { 5, 6, 4 };

we can directly use Integer.valueOf to convert int from string.

If the input value changes to

{ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9} & {9}

then you will face Number format exception.

Oh! So what should we do?

Change Integer.valueOf to Long.valueOf problem will solve, right?

Yes, it will solve for the above input but not for the other one    

{9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9} & {9}.

Again Number format exception, Now, what will be the alternative to the above logic?

Or we have any alternative?

Yes, we have BigInteger

My Solution

 
import java.math.BigInteger;

public class AddTwoNumbers {

	public static void main(String[] args) {
		int[] i1 = new int[] { 2, 4, 3 };
		int[] i2 = new int[] { 5, 6, 4 };

		System.out.println(getValue(addTwoNumbers(createList(i1), createList(i2))));
	}

	private static ListNode createList(int[] input) {
		ListNode root = null;
		ListNode node = null;

		for (int i = 0; i < input.length; i++) {
			ListNode tmp = new ListNode(input[i]);

			if (node != null)
				node.next = tmp;

			node = tmp;

			if (root == null)
				root = tmp;
		}

		return root;
	}

	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		String val1 = getValue(l1);
		String val2 = getValue(l2);
		BigInteger b1 = new BigInteger(val1);
		BigInteger b2 = new BigInteger(val2);
		String result = (b1.add(b2)).toString();

		ListNode resNode = new ListNode();
		ListNode next = null;
		for (int i = 0; i < result.length(); i++) {
			if (next == null) {
				next = resNode;
				resNode.val = Integer.valueOf(String.valueOf(result.charAt(i)));
			} else {
				next = new ListNode();
				next.val = Integer.valueOf(String.valueOf(result.charAt(i)));
				next.next = resNode;
				resNode = next;
			}

		}
		return resNode;
	}

	public static String getValue(ListNode l1) {
		String val = "";
		while (l1 != null) {
			val = l1.val + "" + val;
			l1 = l1.next;
		}
		return val;
	}

	public static class ListNode {
		int val;
		ListNode next;

		ListNode() {
		}

		ListNode(int val) {
			this.val = val;
		}

		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}

}

Thanks for reading :) 

Whether this post is helpful?

Have something to add to this post? If you have any other quick thoughts/hints that you think people will find useful? Share it in the comments. feedback are welcome...