17 Nov 2013

Linked List: Sum two Linked Lists

Problem Statement:
      Given two linked lists, represented as numbers , represent the resultant sum of two linked linked list as a linked list.

Fig: Given Lists and resultant list
     Solution :

Steps Involved: 
  1. Generate the number from both the linked list using addition(Node , int) method.
  2. Add the numbers generated by the linked list to calculate the sum.
  3. Use the generated sum to create a linked list in which nodes are appended in the beggining of the list.

Full Source Code: LINK

 /**
  * Procedure to calulate resultant list
  * @param head1: head of 1st list
  * @param head2: head of 2st list
  * @return
  */
 public Node addLists(Node head1 , Node head2)
 {
  int sum1 = addition(head1,0); //sum of 1st list
  int sum2 = addition(head2,0); //sum of 2nd list
  return createList(sum1 + sum2);
 }
 
 /**
  * Adds all the elements in the list
  * @return added sum
  */
 public int addition(Node head ,int sum){
  if(head==null)
     return sum;
  
  sum = sum*10 + head.data;
  return  addition(head.next , sum) ;
 }
 
 /**
  * Creating list of the total sum Obtained
  * @param totSum is sum of the two list obtained
  * @return head of the new list created
  */
 public Node createList(int totSum){
  Node head=null;
  
  while(totSum > 0){
   int val =totSum%10 ;
   totSum = totSum/10;
   head=insert(val,head);
  }
  
  return head;
 }
 
 /**
  * Inserts node at the beggining
  * @return head of the list
  */
 public Node insert(int val , Node head){
  Node node= new Node(val);
  
  if(head==null)
   head=node;
  else
  {
   node.next = head;
   head=node;
  }
  return head;
 }
 
 /**
  * Prints the new list created
  * @param head
  */
 public void displayList(Node head)
 {
  Node tempNode;
  tempNode=head;
  while(tempNode!=null)
  {
   System.out.print(tempNode.data+"-->");
   tempNode=tempNode.next;
  }
  System.out.print("null");
  System.out.println();
 }

Please comment and post your suggestions or any critiques, they are most welcome.  Feel free.

Happy Coding !! :)

2 comments:

  1. step 1:
    Generate the number from both the linked list using addition(Node , int) method.

    this will take a lot of time, as we need to generate every the numbers every time by traversing the linked lists

    ReplyDelete
    Replies
    1. Didnt get your question buddy , can u elaborate ??

      Delete