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
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