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 !
- Use two string to store the value (iterate the ListNode)
- reverse two string and add them together
- Reverse the answer and iterate generate the ListNode
Let us give that a try !!
C# Solution
❌First try ➡ OverflowException
/**
* Definition for singly-linked list.
* 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[0].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
/**
* Definition for singly-linked list.
* 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
- Initialize
- Too much variable have used
⭐Solution2
/**
* Definition for singly-linked list.
* 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!
/**
* Definition for singly-linked list.
* 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
/**
* Definition for singly-linked list.
* 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 !
The problem link : Add Two Numbers – LeetCode
🧡Here to see the next problem ➡ LeetCode #3 Longest Substring Without Repeating Characters Solution & Explanation – Zyrastory.com
Related Post
That helps a lot!
Ⲕeep on working, grеat job!
Thanks for your kind words🧡
Hi, sum/10 returns a float but sum//10 returns an int ^^
Thks for sharing your code, it helped me figure out what was provided but the runtime environment vs what i had to implement