This blog will soon be merged with

JavaByPatel

which explains each solution in detail, to visit new blog, click JavaByPatel

Sunday, 31 May 2015

Add two numbers represented by linked lists. (Numbers are stored in forward fashion ie least significant digit is at last node.)


package linkedlist.singly;

//Add two numbers represented by linked lists 
// 245   :  5 -> 4 -> 2
// 99789 :  9 -> 8 -> 7 -> 9 -> 9
// Ans   :  99341
public class Add2NumbersInLinkListType2 {

 static int carry=0;
 
 public static void main(String[] args) {

  Node templ11 = new Node(0);
  Node templ12 = new Node(0);
  Node templ13 = new Node(9);

  Node templ21 = new Node(0);
  Node templ22 = new Node(0);
  Node templ23 = new Node(0);
  Node templ24 = new Node(0);
  Node templ25 = new Node(9);

  templ11.setNext(templ12);
  templ12.setNext(templ13);

  templ21.setNext(templ22);
  templ22.setNext(templ23);
  templ23.setNext(templ24);
  templ24.setNext(templ25);

  Node res = findSum(templ11, templ21, 0);
  if(carry==1){
   Node tempNode = new Node(carry);
   tempNode.setNext(res);
   res = tempNode;
  }
  while(res!=null){
   System.out.print(res.getData() + " -> ");
   res=res.getNext();
  }
 }

 private static Node findSum(Node l1, Node l2, int diff){

  int length1 = findLength(l1);
  int length2 = findLength(l2);

  if(length1>length2){
   //l1 having more nodes
   Node res = findSum(l1.getNext(), l2, diff--);
   int data = l1.getData() + carry;
   if(data>9){
    carry=1;
    Node tempNode = new Node(data%10);
    tempNode.setNext(res);
    res = tempNode;
   }else{
    carry=0;
    Node tempNode = new Node(data);
    tempNode.setNext(res);
    res = tempNode;
   }
   return res;

  }else if(length2>length1){
   //l2 having more nodes
   Node res = findSum(l1, l2.getNext(), diff++);
   int data = l2.getData() + carry;
   if(data>9){
    carry=1;
    Node tempNode = new Node(data%10);
    tempNode.setNext(res);
    res = tempNode;
   }else{
    carry=0;
    Node tempNode = new Node(data);
    tempNode.setNext(res);
    res = tempNode;
   }
   return res;

  }else{
   //both have same length
   Node res = findSumForListOfSameSize(l1, l2);
   return res;
  }
 }
 
 private static Node findSumForListOfSameSize(Node l1, Node l2){
  if(l1==null && l2==null)
   return null;

  Node head = findSumForListOfSameSize(l1.getNext(), l2.getNext());

  int temp = l1.getData() + l2.getData() + carry;
  if(temp>9){
   carry=1;
  }else{
   carry=0;
  }

  if(head==null){
   head = new Node(temp % 10);
  }else{
   Node tempNode = new Node(temp % 10);
   tempNode.setNext(head);
   head = tempNode;
  }
  return head;
 }
 
 private static int findLength(Node node){
  int count=0;
  while(node!=null){
   count++;
   node = node.getNext();
  }
  return count;
 }
}



No comments:

Post a Comment