Monday 2 September 2013

Multiply two number represented as Linked List and return the result as Linked list

Ex :
Input : list = 9->9->9
          list2 = 1->2->3

Output : 1228->7->7

class MultiplyLinkedListNumber{
//Tree
static class Node{
int data;
Node next = null;

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

//Utility to insert new node at the end of given list
public void insertAtEnd(int data){
Node newNode = new Node(data);
Node n = this;
while(n.next != null){
n = n.next;
}
n.next = newNode;
}

//Utility function to print the given list
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;
}
}
}

//Function to multiply two given lists 
//return resulted list
static Node multiply(Node head, Node head1){
//Base Condition
if(head == null || head1 == null)
return null;

int number = getNumber(head);  //convert one list into number

//traverse the second list and multiply the number with the current element of the list and store in the new list.
Node current = head1; Node result = null;
while(current != null){
if(result == null){
result = new Node(current.data * number);
}else{
                               //multiply current element with the "number" and store in the new list node
Node temp = new Node(current.data * number);  
temp.next = result;
result = temp;
}
current = current.next;  
}
return process(result);
}

//Utility function
static Node process(Node list){
Node head = list;
int carry = 0, i = 0;
//traverse the given list
while(head != null && head.next != null){
i = head.data;
head.data = (carry + i)%10;
carry = (i+carry)/10;
head = head.next;
}
head.data = head.data + carry;
return reverse(list);
}

//Utility function to reverse the given list
//Ex: Input : 1->2->3
//Output : 3->2->1
static Node reverse(Node list){
if(list == null)
return null;

Node current = list, previous = null, forward;
while(current != null){
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
return previous;
}

//Utility function to convert list into number
//Ex : Input = 1->2->3
//Output = 123
static int getNumber(Node head){
int number = 0;
while(head != null){
number = 10*number + head.data;
head = head.next;
}
return number;
}

public static void main(String... args){
//create the first list
Node list = new Node(9);
list.insertAtEnd(9);
list.insertAtEnd(9);

//create the second list
Node list1 = new Node(1);
list1.insertAtEnd(2);
list1.insertAtEnd(3);

//call the multiply method
Node result = multiply(list, list1);
 
//print the list
result.display();
}
   }

Output : 1228->7->7

Time Complexity : O(N)
Space Complexity : O(1)

No comments:

Post a Comment