C2P5.java

C2P5.java

package chapter2;

/*
 * Career Cup 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 1's 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.
 */
public class C2P5 {

  public static Node reverse(Node head) {
		Node post = null, prev = null;
		while (head != null) {
			post = head;
			head = head.next;
			post.next = prev;
			prev = post;
		}
		return post;
	}
	
	//add digit by digit
	//time:O(n), space:O(n)
	public static Node addInReverseOrder(Node head1, Node head2) {
		Node result = null, pointer = result, pExtra;
		int surplus = 0;
		while (head1 != null && head2 != null) {
			int sum = head1.value + head2.value + surplus;
			if (result == null) {
				pointer = result = new Node(sum % 10);
			} else {
				pointer.next = new Node(sum % 10);
				pointer = pointer.next;
			}
			surplus = sum / 10;
			head1 = head1.next;
			head2 = head2.next;
		}
		if (head1 != null || head2 != null) {
			pExtra = head1 != null ? head1 : head2;
			while (pExtra != null && surplus > 0) {
				int sum = pExtra.value + surplus;
				surplus = sum / 10;
				pointer.next = new Node(sum % 10);
				pointer = pointer.next;
				pExtra = pExtra.next;
			}
		}
		if (surplus > 0)
			pointer.next = new Node(surplus);
		return result;
	}
	
	//reverse, then call the above method
	//time: O(n) space:O(n)
	public static Node addInNormalOrder(Node head1, Node head2) {
		return reverse(addInReverseOrder(reverse(head1), reverse(head2)));
	}

	public static void main(String[] args) {
		int[] array1 = { 7, 1, 6 };
		int[] array2 = { 5, 9, 3, 9 };
		Node head1 = new Node(array1);
		Node head2 = new Node(array2);
		addInReverseOrder(head1, head2).printLinkList();
		addInNormalOrder(head1, head2).printLinkList();
	}
}

Node.java

package chapter2;

public class Node {

  public int value;
	public Node next;

	public Node(int value) {
		this.value = value;
		this.next = null;
	}
	
	public Node(int[] array){
		if (array.length != 0) {
			this.value = array[0];
			this.next = null;
		}
		for (int i = 1; i < array.length; i++) {
			this.appendToTail(array[i]);
		}
	}
	
	
	public void  printLinkList(){
		Node pointer = this;
		while (pointer != null) {
			System.out.printf("%d%s",pointer.value, pointer.next != null ? " -> ":"\n");
			pointer = pointer.next;
		}
	}

	public void appendToTail(int d) {
		Node pointer = this;
		Node node = new Node(d);
		while(pointer.next != null){
			pointer = pointer.next;
		}
		pointer.next = node;
	}
	
	@Override
	public String toString(){
		return String.format("value of node:%d", value);
	}
	
}