add two numbers
Here is the prompt
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.
--
My first thought is a naive approach to take the two linked lists l1 and l2 and convert them to integers somehow, add them together, and present the result as a linked list. However, the number of nodes in each linked list CAN be huge, up to 100 in this question.
Technically, I guess Big Integer in dotnet c sharp can be used to represent an arbitrarily large signed integer. However, lets think about the problem once again. Why did they give us the two numbers stored in reverse order?
How do we add two numbers? we add the ones digits, carry over whatever we need to, and keep going. How do we do this with linked lists?
/**
* 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) {
}
}
I guess the first thing they want to see is if I can even read code and traverse through a linked list. Lets take things one step at a time. I can go from the first List Node to the second pretty easily.
// ListNode l1
ListNode mine = l1.next;
How do I do this in a loop?
while (l1.next != null)
{
l1 = l1.next;
}
That's basically the essense of it, right? You can do things in there with your l1 but the bare essense of traversing through a linked list is basically that above.
We can do better though. It is ok for l1 to be null. So we can remove the dot next in the condition.
while (l1 != null)
{
l1 = l1.next;
}
So, now lets think of a simple case with two linked lists with 1 -> 2 -> 3 and 4 -> 5 -> 6. the sum is 321 + 654 = 975. Notice that there is no carry over here so that makes our life easier. how do we write this as code?
while (l1 != null || l2 != null)
{
// add these two and store it somewhere
int currentResult = l1.val + l2.val;
l1 = l1.next;
l2 = l2.next;
}
what would this code do? At first, we have l1.val = 1 and l2.val = 4, so currentResult is 5. Then, we move on to the next one. l1.val = 2, l2.val = 5, so currentResult is 7. Now, l1.val = 3 and l2.val = 6. So, currentResult = 9.
Now, lets store this result somewhere.
ListNode placeholder = new();
while (l1 != null || l2 != null)
{
placeholder.val = l1.val + l2.val;
placeholder.next = new();
placeholder = placeholder.next();
l1 = l1.next;
l2 = l2.next;
}
return placeholder;
Does this code work for our naive case with no carry over? You might have noticed the problem. We have lost our result! When we keep changing the placeholder to placeholder.next(), we have no way to get back to the original. Let us fix that.
ListNode placeholder = new();
ListNode current = placeholder;
while (l1 != null || l2 != null)
{
current.val = l1.val + l2.val;
current.next = new();
current = current.next();
l1 = l1.next;
l2 = l2.next;
}
return placeholder;
Keep in mind that this is only for the simple case with no carry as explained above. How does it look?
The result is still wrong.
/**
* 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) {
ListNode placeholder = new();
ListNode current = placeholder;
while (l1 != null || l2 != null)
{
current.val = l1.val + l2.val;
current.next = new();
current = current.next;
l1 = l1.next;
l2 = l2.next;
}
return placeholder;
}
}
With [1, 2, 3] as l1 and [4, 5, 6] as l2, we expect [5,7,9] as output but above we get [5,7,9,0]. Where did this extra zero come from?
/**
* 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) {
ListNode placeholder = new();
ListNode current = placeholder;
while (l1 != null || l2 != null)
{
current.val = l1.val + l2.val;
current.next = new();
current = current.next;
l1 = l1.next;
l2 = l2.next;
}
return placeholder.next;
}
}
Now, the result is [7,9,0].
Lets go back to our earlier code and fix just this issue. We will check if l1 or l2 is null and only add a new node if at least one of them is not null.
/**
* 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) {
ListNode placeholder = new();
ListNode current = placeholder;
while (l1 != null || l2 != null)
{
current.val = l1.val + l2.val;
l1 = l1.next;
l2 = l2.next;
if (l1 != null || l2 != null)
{
current.next = new();
current = current.next;
}
}
return placeholder;
}
}
This fixes our immediate concern. Now, we can concentrate on the carry problem. because each node can only be 0-9, we should consider carry, even for small problems. Adding any two numbers that result in ten or more for example, five and seven. The result of adding five and seven is twelve. Here, there is only one element in each list with no next but the result should clearly have two items.
ListNode placeholder = new();
ListNode current = placeholder;
while (l1 != null || l2 != null)
{
current.val = l1.val + l2.val;
l1 = l1.next;
l2 = l2.next;
if (l1 != null || l2 != null)
{
current.next = new();
current = current.next;
}
}
return placeholder;
First things first, we can no longer simply add l1.val and l2.val. We need to somehow only keep the ones position of the addition. For example, when adding five and seven, we need to only keep the two.
ListNode placeholder = new();
ListNode current = placeholder;
while (l1 != null || l2 != null)
{
current.val = (l1.val + l2.val) % 10;
l1 = l1.next;
l2 = l2.next;
if (l1 != null || l2 != null)
{
current.next = new();
current = current.next;
}
}
return placeholder;
Lets see if this breaks our existing test. It should not. and it did not. because if a number is smaller than ten then modulo ten gives the same number back so nothing has changed there.
Now, lets add our carry.
ListNode placeholder = new();
ListNode current = placeholder;
int carry = 0;
while (l1 != null || l2 != null)
{
current.val = (l1.val + l2.val + carry) % 10;
carry = (l1.val + l2.val + carry) / 10;
l1 = l1.next;
l2 = l2.next;
if (l1 != null || l2 != null || carry > 0)
{
current.next = new();
current = current.next;
}
}
return placeholder;
We have another problem. If l1 and l2 are of unequal sizes for example, l1 = [9,9,9,9,9,9,9] and l2 = [9,9,9,9]
Unhandled exception. System.NullReferenceException: Object reference not set to an instance of an object.
At Solution.AddTwoNumbers(ListNode l1, ListNode l2)
At __DriverSolution__.__Helper__(ListNode param_1, ListNode param_2)
At __Driver__.Main(String[] args)
We need to check for nulls.
ListNode placeholder = new();
ListNode current = placeholder;
int carry = 0;
while (l1 != null || l2 != null)
{
// current.val = (l1.val + l2.val + carry) % 10;
int currentVal = 0;
if (l1 != null)
{
currentVal += l1.val;
l1 = l1.next;
}
if (l2 != null)
{
currentVal += l2.val;
l2 = l2.next;
}
currentVal += carry;
current.val = currentVal % 10;
carry = currentVal / 10;
if (l1 != null || l2 != null || carry > 0)
{
current.next = new(carry);
current = current.next;
}
}
return placeholder;
/**
* 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) {
ListNode placeholder = new();
ListNode current = placeholder;
int carry = 0;
while (l1 != null || l2 != null)
{
// current.val = (l1.val + l2.val + carry) % 10;
int currentVal = 0;
if (l1 != null)
{
currentVal += l1.val;
l1 = l1.next;
}
if (l2 != null)
{
currentVal += l2.val;
l2 = l2.next;
}
currentVal += carry;
current.val = currentVal % 10;
carry = currentVal / 10;
if (l1 != null || l2 != null || carry > 0)
{
current.next = new(carry);
current = current.next;
}
}
return placeholder;
}
}