Add two numbers represented by linked lists using recursive

Add two numbers represented by linked lists using recursive

Addition of 2 Linked List  

Add two numbers represented by linked lists using recursive method and generate the 3td linked with addition of 1st and 2nd linked list.

For example:

val_1[] = {       7, 6, 5 }

val_2[] = { 9, 6, 4, 1, 6 }

then the output should be {9, 7, 1, 8, 1} basically its addition of 1st and 2nd linked lists as same normal 2 numbers addition.

         
Let's see simple java code to create linked lists using input array and to get the addition of 2 linked list in 3rd linked list.

public class SumOfTwoLL {
 
 class NODE {

  int data;
  NODE next;

  public NODE(int data) {
   this.data = data;
   this.next = null;
  }
 }

 public static void main(String[] args) {

  SumOfTwoLL obj = new SumOfTwoLL();
  
  int val_1[] = new int[] {       7, 6, 5 };
  int val_2[] = new int[] { 9, 6, 4, 1, 6 };

  // Create linked list out of arrays
  NODE first = obj.createLinkedList(val_1);
  NODE second = obj.createLinkedList(val_2);
  
  // Check no. of nodes in both Linked list
  int t1 = obj.noOfNodes(first);
  int t2 = obj.noOfNodes(second);
  
  // Adjusting Linked List with leading zero node's to make it equal size
  if(t1 < t2) first = obj.adjustLinkedList(first, (t2-t1));
  else if(t2 < t1) second = obj.adjustLinkedList(second, (t1-t2));
  
  // add method call
  NODE third = obj.addTwoLL(first, second, 0);
  
  obj.print(third);
  
 }
 
 // Method to get sum of 2 Linked List
 private NODE addTwoLL(NODE first, NODE second, int cnt) {
  
  if(first != null && second != null){
   
   // Recursive call moving to last node 
   NODE node = addTwoLL(first.next, second.next, cnt+1);
   
   // Calculating sum from last 2 values 
   int val = (first.data + second.data) +node.data;
   
   int carry = val/10;
   int sum = val%10;
   
   // If carry present or not the first node in list then create a node with carry value
   if(cnt != 0 || carry > 0) {
   
    NODE carryNode = new NODE(carry);
    node.data = sum;
    carryNode.next = node;
    return carryNode;
   
   }else {
    // Assign final sum to the previous cycle carry node
    node.data = sum;
    return node;
   }
  }
  // Create last carry node with zero
  return new NODE(0);
 }
 

 private NODE adjustLinkedList(NODE ll, int noOfNodesToAdd){
  while(noOfNodesToAdd > 0){
   NODE tmp = new NODE(0);
   tmp.next = ll;
   ll = tmp;
   noOfNodesToAdd--;
  }
  return ll;
 }
 
 
 private int noOfNodes(NODE ll){
  int count = 0;
  while(ll !=  null){
   count ++;
   ll = ll.next;
  }
  return count;
  
 }
 
 public NODE createLinkedList(int val[]) {
  NODE start = null;
  for (int i : val) {
   NODE tmp = new NODE(i);
   if (start == null) {
    start = tmp;
   } else {
    NODE mover = start;
    while (mover.next != null) {
     mover = mover.next;
    }
    mover.next = tmp;
   }
  }
  return start;
 }
 

 public void print(NODE tmp){
  while(tmp != null ){
   System.out.print(tmp.data +", ");
   tmp = tmp.next;
  }
 }
}

OUTPUT:

9, 7, 1, 8, 1,