Tuesday 3 September 2013

Add two numbers represented as linkedlist

Add two numbers represented as linkedlist.

Example
Input : list1: 7->1->6   (617)
          list2: 5->9->2    (295)
 Output: 2->1->9   (915)

Implementation

class AddLinkedListNumber{
//LinkedList
static class Node{
int data;
Node next = null;

public Node(int data){
this.data = data;
}

//Utility to add new linkedlist node at the end of existing list
public void insertAtEnd(int data){
Node newNode = new Node(data);
Node n = this;

while(n.next != null){
n = n.next;
}
n.next = newNode;
}

//method to add 2 lists
public static Node addLists(Node n1 , Node n2 , int carry){
//Boundary Condition
if(n1 == null && n2 == null && carry == 0)
return null;

Node result = new Node(carry);
int value = carry;
 
                        if(n1 != null)
value += n1.data;

if(n2 !=null)
value += n2.data;

result.data = value%10; //second digit of number

//recurse
if(n1 != null || n2 !=null || value >= 10){
Node more = addLists(n1 == null ? null:n1.next,
n2 == null ? null:n2.next,
value >=10 ? 1 : 0);

result.next = more;
}
return result;
}

//Utility to display linkedlist
public void display(){
Node head = this;

while(head != null){
if(head.next !=null)
System.out.print(head.data+"->");
else
System.out.print(head.data);
head = head.next;
}
}
}

public static void main(String []args){
Node list = new Node(7);;
Node list2 =  new Node(5);

list.insertAtEnd(1);
list.insertAtEnd(6);

list2.insertAtEnd(9);
list2.insertAtEnd(2);

  Node result = Node.addLists(n1,n2,0);
result.display();
}
 }

Output:
2->1->9

No comments:

Post a Comment