/**
 * You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. 
　　Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) 
　　Output: 7 -> 0 -> 8 
 */

/**
 * 有两个单链表，代表两个非负数，每一个节点代表一个数位，数字是反向存储的，即第一个结点表示最低位，最后一个结点表示最高位。求两个数的相加和，并且以链表形式返回。 
 */

package AddTwoNumber;

public class AddTwoNumberApp {
	public static Link addTwoNumder(Link l1,Link l2) {
		Link tmpLink = new Link();
		
		if(l1.isEmpty())	return l2;
		if(l2.isEmpty())	return l1;
		
		Node current_l1 = l1.first;
		Node current_l2 = l2.first;
		int carry = 0;	//进阶数字
		int val = 0;
		
		while(current_l1 != null && current_l2 != null) {
			val = (current_l1.iData + current_l2.iData + carry)%10;
			carry = (current_l1.iData + current_l2.iData + carry)/10;
			tmpLink.insert(val);
			
			current_l1 = current_l1.next;
			current_l2 = current_l2.next;
		}
		
		
		while(current_l1 != null) {
			val = (current_l1.iData + carry) % 10;
			carry = (current_l1.iData + carry) / 10;
			tmpLink.insert(val);
		}
		
		while(current_l2 != null) {
			val = (current_l2.iData + carry) % 10;
			carry = (current_l2.iData + carry) / 10;
			tmpLink.insert(val);
		}
		
		if(carry!= 0) {
			tmpLink.insert(carry);
		}
		
		return tmpLink;
	}
	public static void main(String[] args) {
		Link link1 = new Link();
		link1.insert(2);
		link1.insert(1);
		
		Link link2 = new Link();
		link2.insert(1);
		link2.insert(9);
		
		Link link3 = addTwoNumder(link1,link2);
		link3.display();
		
	}
}