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.T…

CC150-2.5.java

/**
 * 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.
 * 
 * @Runtime & spaces
 * runtime: O(m+n)
 * space:   O(max(m,n))
*/
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main so = new Main();
		ListNode a = new ListNode(1);
		ListNode b = new ListNode(9);
		ListNode c = new ListNode(8);
		ListNode d = new ListNode(9);
		ListNode e = new ListNode(7);
		ListNode f = new ListNode(3);
	//	ListNode g = new ListNode(6);
		a.next = b;
		b.next = c;
		
		d.next = e;
		e.next = f;
//		f.next = g;
		ListNode p = so.addList(a, d);
		while (p != null) {

			System.out.println(p.val);
			p = p.next;
		}
	}

	public ListNode addList(ListNode l1, ListNode l2) {
		if (l1 == null || l2 == null)
			return null;
		int carry = 0;
		ListNode result = new ListNode(0);
		ListNode resultStart = result;
		while (l1 != null && l2 != null) {
			int temp = l1.val + l2.val + carry;
			if (temp < 10) {
				carry = 0;
				result.next = new ListNode(temp);
			} else {
				temp -= 10;
				carry = 1;
				result.next = new ListNode(temp);
			}
			result = result.next;
			l1 = l1.next;
			l2 = l2.next;
		}
		while (l1 != null) {
			int temp = l1.val + carry;
			if (temp < 10) {
				carry = 0;
				result.next = new ListNode(temp);
			} else {
				temp -= 10;
				carry = 1;
				result.next = new ListNode(temp);
			}
			result = result.next;
			l1 = l1.next;
		}
		while (l2 != null) {
			int temp = l2.val + carry;
			if (temp < 10) {
				carry = 0;
				result.next = new ListNode(temp);
			} else {
				temp -= 10;
				carry = 1;
				result.next = new ListNode(temp);
			}
			result = result.next;
			l2 = l2.next;
		}
		if (carry == 1)
			result.next = new ListNode(1);
		return resultStart.next;
	}
	
	//============================================================================
	//FOLLOW UP
	//see next gist
}