 # LeetCode #2 Add Two Numbers Solution & Explanation

Content

## LeetCode Problem

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.

## Solution

When I first saw this question, I thought that was so easy !

1. Use two string to store the value (iterate the ListNode)
2. reverse two string and add them together
3. Reverse the answer and iterate generate the ListNode

Let us give that a try !!

### C# Solution

First tryOverflowException

``````/**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int val=0, ListNode next=null) {
*         this.val = val;
*         this.next = next;
*     }
* }
*/
public class Solution {
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
string tmp1 = "";
string tmp2 = "";

while(l1!=null)
{
tmp1+=l1.val.ToString();
l1 = l1.next;
}

while(l2!=null)
{
tmp2+=l2.val.ToString();
l2 = l2.next;
}

char[] charArray = tmp1.ToCharArray();
Array.Reverse(charArray);
tmp1 =  new string(charArray);

charArray = tmp2.ToCharArray();
Array.Reverse(charArray);
tmp2 =  new string(charArray);

string res = (Convert.ToInt32(tmp1)+Convert.ToInt32(tmp2)).ToString();
Console.WriteLine(res);

charArray = res.ToCharArray();
Array.Reverse(charArray);
res =  new string(charArray);

ListNode resNode = new ListNode();
ListNode copyNode = resNode;
copyNode.val = Convert.ToInt32(res.ToString());

for(int i = 1;i<res.Length;i++)
{
ListNode newNode = new ListNode();

newNode.val = Convert.ToInt32(res[i].ToString());
copyNode.next = newNode;

copyNode = newNode;
}

return resNode;

}
}``````

And what I got was an exception!

We can see that it shows value was too large for an Int32

Int32 MaxValue : 2147483647 (231-1) < 9999999991 ( the test case)

Even if the number pass, time spent won’t be so good ( with too much conversion )

Maybe, we should try another way to solve the problem.

Solution1

``````/**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int val=0, ListNode next=null) {
*         this.val = val;
*         this.next = next;
*     }
* }
*/
public class Solution {
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
bool next = false;
int res = 0;

//first init
ListNode resNode = new ListNode();
ListNode copyNode = new ListNode();

res = l1.val+l2.val;
if(res>9)
{
next = true;
res -=10;
}
resNode.val = res;
copyNode = resNode;

l1 = l1.next;
l2 = l2.next;

//start iteration
while(l1!=null || l2!=null)
{

int tmp1 = 0;
int tmp2 = 0;

if(l1!=null)
{
tmp1 = l1.val;
l1 = l1.next;
}

if(l2!=null)
{
tmp2 = l2.val;
l2 = l2.next;
}

res = tmp1+tmp2;
if(next)
{
res+=1;
next = false;
}

if(res>9)
{
next = true;
res -=10;
}

ListNode newNode = new ListNode();
newNode.val = res;
copyNode.next = newNode;
copyNode = newNode;

}

if(next)
{
ListNode newNode = new ListNode();
newNode.val = 1;
copyNode.next = newNode;
}

return resNode;
}
}``````

In this solution, we combined calculate number and generate ListNode in same iteration.

Without using a very big integer to calculate .

But the code seems a little complex, can we optimize the code? Sure!

Let us optimize the two section of the code

1. Initialize
2. Too much variable have used

Solution2

``````/**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int val=0, ListNode next=null) {
*         this.val = val;
*         this.next = next;
*     }
* }
*/
public class Solution {
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
int sum = 0;

//first init
ListNode resNode = new ListNode();
ListNode copyNode = resNode;

//start iteration
while(l1!=null || l2!=null || sum!= 0)
{
if(l1!=null)
{
sum += l1.val;
l1 = l1.next;
}

if(l2!=null)
{
sum += l2.val;
l2 = l2.next;
}

ListNode newNode = new ListNode();
newNode.val = sum%10;
copyNode.next = newNode;
copyNode = newNode;

sum/=10;   //will always be 0 or 1
}

return resNode.next;
}
}``````

We use variable 【sum】 to replace ➡ 【next】and【res】in the first solution

### Java Solution

Solution1 ➡ Just copy C# solution2 haha!

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int sum = 0;

//first init
ListNode resNode = new ListNode();
ListNode copyNode = resNode;

//start iteration
while(l1!=null || l2!=null || sum!= 0)
{
if(l1!=null)
{
sum += l1.val;
l1 = l1.next;
}

if(l2!=null)
{
sum += l2.val;
l2 = l2.next;
}

ListNode newNode = new ListNode();
newNode.val = sum%10;
copyNode.next = newNode;
copyNode = newNode;

sum/=10;   //will always be 0 or 1
}

return resNode.next;
}
}``````

Runtime : 2ms

### Python3 Solution

Solution1

``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
sum = 0;

#first init
resNode = ListNode();
copyNode = resNode;

#start iteration
while(l1!=None or l2!=None or sum!= 0):
if(l1!=None):
sum += l1.val;
l1 = l1.next;

if(l2!=None):
sum += l2.val;
l2 = l2.next;

newNode = ListNode();
newNode.val = sum%10;
copyNode.next = newNode;
copyNode = newNode;

sum= int(sum/10);

return resNode.next;``````

【sum】 needs to convert to Integer. Otherwise it will be a float number.

⬆ We need 0 or 1 for next iteration.

### JavaScript Solution

Solution1

``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
var sum = 0;

//first init
var resNode = new ListNode();
var copyNode = resNode;

//start iteration
while(l1!=undefined || l2!=undefined || sum!= 0)
{
if(l1!=undefined)
{
sum += l1.val;
l1 = l1.next;
}

if(l2!=undefined)
{
sum += l2.val;
l2 = l2.next;
}

var newNode = new ListNode();
newNode.val = sum%10;
copyNode.next = newNode;
copyNode = newNode;

sum = parseInt(sum/10);

}

return resNode.next;

};``````

Same as python3, we need to set 【sum】 as integer.

## Conclusion

This problem is the first Medium problem of LeetCode, maybe may people get stuck on it when they first saw it (just like me), hope this article can help you!

🧡If my solution helps, that is my honor!

🧡Clicking any ad can help me to pay the hosting fee ! Thank you !

🧡Here to see the next problem ➡ LeetCode #3 Longest Substring Without Repeating Characters Solution & Explanation – Zyrastory.com

Related Post

1. #### Jessica

That helps a lot!

2. #### elegantly

Ⲕeep on working, grеat job!