Showing posts with label Addition of 2 Linked List. Show all posts
Showing posts with label Addition of 2 Linked List. Show all posts

Add two numbers represented by linked lists using recursive

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.

Add two numbers represented by linked lists using recursive

         
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,