# Why is my Java Solution so Slow?

• I'm a C++ developer by trade but am doing these exercises in an attempt to gain competence in Java.

I have developed a solution to this problem but it only beats 31.63% of javasubmissions, however to me it looks functionally identical to 'UpTheHell's solution which reportedly beats 98% of solutions. I'm just wondering what it is that is so expensive in my solution.

My solution:

``````public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// Quick Return if only 1 number
if(l1==null) return l2;
if(l2==null) return l1;

// Dummy node used to start the list
ListNode newNode = new ListNode(-1);
ListNode rv = newNode;

// Declare variables before loop
int carry=0, digitSum;

// Loop over all input digits
while (l1 != null || l2 != null || carry != 0)
{
digitSum=carry;

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

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

newNode.next = new ListNode(digitSum % 10);
carry = digitSum / 10;

newNode = newNode.next;
}

// Return node after dummy
return rv.next;
}
}
``````

UpTheHell's ssolution:

``````public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1==null) return l2;
if(l2==null) return l1;

int carry=0;

while(carry>0 || l1!=null || l2!=null){ //check if next node exsits
int n1=l1==null?0:l1.val;  // get value of number 1
l1=l1.next;

int n2=l2==null?0:l2.val; // get value of number 2
if(l2!=null)
l2=l2.next;

int sum=n1+n2+carry;
carry=sum/10; // calculate carry

ListNode cur=new ListNode(sum%10);
tail.next=cur;
tail=cur; // add node at the end of tail
}
}

}
``````

• I suggest you submit UpTheHell's solution and see what happens.

• @StefanPochmann
Yeah, I actually did try running his and it fails due to the missing "Null check" for the line `l1=l1.next;`.

When I added the null check his solution came out at about 31% as well so I figured I'd misunderstood something.

Is it possible that UpTheHell's solution was in the top 2 percentile when it was first written but that it's now slipped to 31%? That seems a long way to slide. Is it likely that UpTheHill simply lied about how many submissions this solution beat. Seems a silly lie to tell as surely you're bound to be caught out, but the fact that there is that missing null check seems odd too.

In any event, even if UpTheHill's solution is invalid can anyone see how to improve my solution. It seems close to optimal as it is but 31% is surprisingly low.

One improvement I was considering was that if one number runs out of digits, and there is no carry you could just tack the remainder of the remaining number on the end of your answer thus preventing the need to create new nodes.

As in for 1,000,001 + 1 you could simply reuse many of the original numbers digits:

``````[0] -> [0] -> [0] -> [0] -> [0] -> [0] -> [1]
[1]     ^
=      |
[2] - - +
``````

• Is it possible that UpTheHell's solution was in the top 2 percentile when it was first written but that it's now slipped to 31%?
That seems a long way to slide.

Not really. Could be the difference between 3.49 ms and 3.50 ms or between 3.99 and 4.00 (depending on how leetcode rounds, which I don't know).

Also, a large test case was added just recently, and the statistics probably still include the times from before.

• Man. I just implemented a recursive solution that takes advantage of using the tail of long numbers as discussed above, and I'm still coming in at 31.63%

``````public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2, int carry) {
// Quick Return if only 1 number.
if (carry == 0)
{
if (l1==null) return l2;
if (l2==null) return l1;
}

int digitSum = (l1==null?0:l1.val) + (l2==null?0:l2.val) + carry;

// Create a new node for the first digit
ListNode newNode = new ListNode(digitSum % 10);

// Recersivly append the next digit.