CODEWITHSUNDEEP
javaalgorithmdata-structures
devyan91
devyan91

Reputation: 99

How do I add two integers represented as two non-empty linked lists?

Question: 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 contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except 0 itself **

Example: Working testcase is as follows: - Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) - Output: 7 -> 0 -> 8 - Explanation: 342 + 465 = 807.

My solution is not working for the following testcase:

Definition for singly-linked list:

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

This is my solution

import java.lang.Math;

class Solution 
{

public ListNode addTwoNumbers(ListNode l1, ListNode l2) 
{
        int count = 0;
        int number1=0;
        int number2=0;
        int temp=0;

        while(l1 !=null)
        {
            temp = l1.val;
            number1 += temp*Math.pow(10,count);
            count++;
            l1= l1.next;
         }

        count = 0;

        while(l2 !=null)
        {
            temp = l2.val;
            number2 += temp*Math.pow(10,count);
            count++;
            l2= l2.next;
        }

        int sum = number1 + number2;
        ListNode l3 = new ListNode(sum%10);
        ListNode l4 = l3;

        while(sum!=0)
        {
          sum=sum/10;
          if (sum!=0) 
          {
          l3.next = new ListNode(sum%10);
          l3=l3.next; 
          } 

        }
        return l4;  

 }
}

Upvotes: 0

Views: 2106

Answers (2)

Boby Robert
Boby Robert

Reputation: 94

although your logic seems fine, this might run into overflow cases when you encounter large test cases/large numbers represented as a linked lists.

I'll give you a suggestion, don't convert the linked list nodes to a number. There's a way to do it another way around just by normal iteration of linked lists.

Try to think about how you would normally add numbers like the way we were taught in school by writing it down on paper.

Upvotes: 1

Anonymous
Anonymous

Reputation: 86276

You have integer overflow. [1,9,9,9,9,9,9,9,9,9] should represent the number 9 999 999 991. You are trying to convert the list to an int (number1), but the largest number that an int can hold is 2 147 483 647 because an int is a signed 2-complement 32 bit integer.

In this situation it would have been really nice if Java would throw an exception to make us aware why it doesn’t work. No such luck. Instead it simply throws away the high-order bits exceeding 32 bits, giving some nonsense negative value (negative because the sign bit (the first bit) happens to be 1).

So what you need to do is perform the addition directly as linked lists without converting to int and back. You can very comfortably have three linked lists each containing up to 11 elements (and also up to a million elements if you needed that), so this will cause no overflow.

If you don’t know what numeric overflow is, please look it up. Your search engine is your friend.

Upvotes: 2

Related Questions