Pages

09/04/2017

[Java] LinkedList sum

Here's a simple exercise: given two positive numbers represented as linked lists, return their sum as a new linked list.

This is quite easy if we represent the two integers with lists that have the least significant digit at the head, eg:

A = 123 -> 3,2,1
B = 45 -> 5,4
result = 168 -> 8,6,1

You can check the code and some tests on my Gist (LinkedListSumJTests):

 /*  
   Given two lists representing integer numbers  
   with the least significant digit in the head position  
   return a new list containing the sum  
   */  
   public static SingleLinkedListNode sumListsFromLSD(SingleLinkedListNode x, SingleLinkedListNode y){  
     if(x == null && y == null) return null;  
   
     int carry = 0, curr = 0, val = 0;  
     SingleLinkedListNode result = null, n = null;  
   
     //keep going until we have data in either list and do not forget the last carry!  
     while(x != null || y != null || carry != 0){  
       curr = ((x == null || x.id == null) ? 0 : x.id) + ((y == null || y.id == null) ? 0 : y.id) + carry; //x + y + carry  
       val = curr % 10; //take only LSD  
   
       //track if we have a carry  
       carry = (curr >= 10) ? 1 : 0;  
   
       if(n == null){  
         n = new SingleLinkedListNode(val);  
         result = n;  
       }  
       else{  
         n.next = new SingleLinkedListNode(val);  
         n = n.next;  
       }  
   
       //move to next digit  
       if(x != null) x = x.next;  
       if(y != null) y = y.next;  
   
     }  
   
     return result;  
   }  

No comments:

Post a Comment

With great power comes great responsibility