Thursday, May 10, 2012

Adding two linked lists


Given 2 singly linked lists which have single digit data, add the two lists and return a new list.

For e.g.

list1: 4->5->5->9->8
list2:      2->3->1->1

Output should be: 4->7->9->0->9

Approach 1: One of the approach can be to reverse both the linked list and then add node by node. In that case you will need to reverse the output list as well.

Approach 2: The other approach is to put the linked lists in the stack. This avoids the need to reverse the lists.
 
public static Node addLinkedLists(Node head1, Node head2)
 {
  if(head1 == null)
   return head2 != null ? head2 : null;
  
  if(head2 == null)
   return head1 != null ? head1 : null;
  
  Stack<node> s1 = new Stack<node>();
  Stack<node> s2 = new Stack<node>();
  Stack<node> s3 = new Stack<node>();
  
  Node list1 = head1;
  Node list2 = head2;
  
  while(list1 != null)
  {
   s1.push(list1);
   list1 = list1.next;
  }
  
  while(list2 != null)
  {
   s2.push(list2);
   list2 = list2.next;
  }
  
  int carry = 0;
  
  while(!s1.empty() &amp;&amp; !s2.empty())
  {
   int total = carry + s1.pop().data + s2.pop().data;
   Node n = new Node(total%10);
   s3.push(n);
   carry = total/10;
  }
  
  while(!s1.empty())
  {
   int total = carry + s1.pop().data;
   Node n = new Node(total%10);
   s3.push(n);
   carry = total/10;
  }
  
  while(!s2.empty())
  {
   int total = carry + s2.pop().data;
   Node n = new Node(total%10);
   s3.push(n);
   carry = total/10;
  }
  
  Node result = s3.pop();
  Node retHead = result;
  
  while(!s3.empty())
  {
   Node n = s3.pop();
   result.next = n;
   result = n;
  }
  
  return retHead;
 }


Both approaches have similar run time complexity but the stack based approach requires more space.


No comments:

Post a Comment