cc150_2.5

gistfile1.java

package cc150;
/*
 * 2.5 You have two numbers represented by a linked list, where each node contains a
single digit. The digits are stored in reverse order, such that the Ts digit is at the
head of the list. Write a function that adds the two numbers and returns the sum
as a linked list.
EXAMPLE
Input: (7-> 1 -> 6) + (5 -> 9 -> 2).That is, 617 + 295.
Output: 2 -> 1 -> 9.That is, 912.
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem.
EXAMPLE
Input: (6 -> 1 -> 7) + (2 -> 9 -> 5).That is, 617 + 295.
Output: 9 -> 1 -> 2.That is, 912
Algorithm:
use an  variable to  store the carry,  from the second one  add the carry  and two numbers, if one  list reach the end  copy the other list's rest
O(m+n) O(M+n)

Follow up   :
 
 use two stacks  to push the  two linked List  and pop up  them and  calculate, 
 if the stack is not  allowed,  we could do  two temp Linklist  to reverse the   two original  link list  then calculate.   below gives the  reverse Linked list method.  
 
 Note :  review the book solutions  I dont think it is  better than mine but   it is the book solution
 */
		
public class AddTwoNumber_2_5 {

	public static void main(String[] args) {
	
		SingleDigitNode firstList= new SingleDigitNode();
		firstList.data =  2;
		SingleDigitNode current = firstList;
		SingleDigitNode newNode = new SingleDigitNode();
		newNode.data = 9 ;
		current.next = newNode;
		current = current.next;
		
		newNode = new SingleDigitNode();
		newNode.data = 5 ;
		current.next = newNode;
		current = current.next;

		newNode = new SingleDigitNode();
		newNode.data = 3 ;
		current.next = newNode;
		
		
		SingleDigitNode secondList= new SingleDigitNode();
		secondList.data =  7;
	
		current = secondList;
		newNode = new SingleDigitNode();
		newNode.data =  2;
		current.next = newNode;
		current = current.next;
		
		newNode = new SingleDigitNode();
		newNode.data =  6;
		current.next = newNode;
		current = current.next;
		
		newNode = new SingleDigitNode();
		newNode.data =  1;
		current.next = newNode;
		current = current.next;
		
		newNode = new SingleDigitNode();
		newNode.data =  2;
		current.next = newNode;
		current = current.next;
		
		newNode = new SingleDigitNode();
		newNode.data = 3 ;
		current.next = newNode;
		
		SingleDigitNode result = addTwoList(firstList, secondList);
		current = result;
		while(current != null){
			System.out.println(current.data);
			current = current.next;
			
		}
		
		System.out.println("======Follow Up==============");
		SingleDigitNode firstReversedList = reverseList(firstList);
		SingleDigitNode secondReversedList = reverseList(secondList);
		SingleDigitNode result2 = addTwoList(firstReversedList, secondReversedList);
		current = result2;
		while(current != null){
			System.out.println(current.data);
			current = current.next;
			
		}
	}

	private static SingleDigitNode addTwoList(SingleDigitNode firstList,
			SingleDigitNode secondList) {
		if(firstList == null) 
			return secondList;
		if(secondList == null)
			return firstList;
		SingleDigitNode result =  new SingleDigitNode();
		SingleDigitNode current = null;
		int carry =0;
		while(firstList !=null && secondList!=null){
			if(current ==null){
				current = result;
			}
			else {
				SingleDigitNode newNode = new SingleDigitNode();
				current.next = newNode;
				current = current.next;
			}
			int sum = firstList.data + secondList.data + carry;
			if(sum >=10) {
				current.data = sum -10;
				carry =1;
			}
			else{
				current.data = sum ;
				carry =0;
			}
			firstList = firstList.next;
			secondList = secondList.next;
		}
		if(firstList == null){
			while(secondList!=null){
				
					SingleDigitNode newNode = new SingleDigitNode();
					current.next = newNode;
					current = current.next;
					int sum =  secondList.data + carry;
					if(sum ==10) {
						current.data = 0;
						carry =1;
					}
					else{
						current.data = sum ;
						carry =0;
					}
				secondList = secondList.next;
			}
		}
		if(secondList == null){
			while(firstList!=null){
				
					SingleDigitNode newNode = new SingleDigitNode();
					current.next = newNode;
					current = current.next;
					int sum =  firstList.data + carry;
					if(sum ==10) {
						current.data = 0;
						carry =1;
					}
					else{
						current.data = sum ;
						carry =0;
					}
					firstList = firstList.next;
				
			}
		}		return result;
	}

	public static  SingleDigitNode reverseList(SingleDigitNode node){
		SingleDigitNode reversedList = null;
		while(node!=null){
			SingleDigitNode newNode = new SingleDigitNode();
			newNode.data = node.data;
			if(reversedList == null)
				reversedList= newNode;
			else{
				newNode.next = reversedList;
				reversedList = newNode;
			}
			node = node.next;	
		}
		return reversedList;
	}
}
class SingleDigitNode {
	int data;
	SingleDigitNode next;
	public SingleDigitNode(){
	}
}