detailed description: See the description of CC150-2.5

CC150-2.5-followUp.java

public class Main {

	/**
	 * 2.5 
	 *  
	 * 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.
	 * 
	 * Solution:
	 * 参考书上答案：
	 * 1.先得到L1和L2的长度，如果不相同，则在前边补0使得位数相同
	 * 2.运用递归的方法，从最后一位开始加起
	 * 
	 * @Runtime & spaces
	 * runtime: O(m+n)
	 * space:   O(max(m,n))
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main so = new Main();
		ListNode a = new ListNode(6);
		ListNode b = new ListNode(1);
		ListNode c = new ListNode(7);
		
		ListNode d = new ListNode(2);
		ListNode e = new ListNode(9);
		ListNode f = new ListNode(6);
		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 len1 = getLength(l1);
		int len2 = getLength(l2);
		if (len1 < len2) {
			l1=padList(l1, len2 - len1);
		} else if (len1 > len2) {
			l2=padList(l2, len2 - len1);
		}
		ListNode head=add(l1,l2);
		if(head.val>=10){
			head.val-=10;
			ListNode newHead=new ListNode(1);
			newHead.next=head;
			head=newHead;
		}
		return head;
	}

	private ListNode add(ListNode l1, ListNode l2) {
		// TODO Auto-generated method stub
		if (l1 == null && l2 == null)
			return null;
		ListNode head = add(l1.next, l2.next);
		ListNode newHead = new ListNode(l1.val + l2.val);
		newHead.next=head;
		if(head!=null){
			newHead.val+=head.val/10;
			head.val=head.val%10;			
		}
		return newHead;
	}

	private ListNode padList(ListNode n, int padLength) {
		// TODO Auto-generated method stub
		ListNode head = n;
		for (int i = 0; i < padLength; i++) {
			ListNode newHead = new ListNode(0);
			newHead.next = head;
			head = newHead;
		}
		return head;
	}

	private int getLength(ListNode n) {
		// TODO Auto-generated method stub
		int count = 1;
		while (n != null) {
			n = n.next;
			count++;
		}
		return count;
	}
}