LinkLists 两个链表相加 @CareerCup

原文：

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: (3 -> 1 -> 5), (5 -> 9 -> 2)

Output: 8 -> 0 -> 8

译文：

你有两个由单链表表示的数。每个结点代表其中的一位数字。数字的存储是逆序的， 也就是说个位位于链表的表头。写一函数使这两个数相加并返回结果，结果也由链表表示。

例子：(3 -> 1 -> 5), (5 -> 9 -> 2)

输入：8 -> 0 -> 8

思路：递归

1） 如果整数在链表中是以倒置方式存放的，那么容易相加

2） 如果整数在链表中是以顺序方式存放的，那么要 1先分别计算两个链表长度 2 把短的链表短的部分补零，使得两链表长度相同 3 递归相加，返回值用一个WrapperNode，不光存放相加后的节点，而且存放carry值。 所以用到方法有：length，padList，addListsHelper，insertBefore

值得主义的情况有：1.链表为空。2.有进位。3.链表长度不一样。

package LinkLists;

import CtCILibrary.LinkedListNode;

public class S2_5 {

	// 当值以reverse order存放在链表时，递归
	// 如：         9->9->9
	// 			+ 1
	//          = 0->0->0->1
	public static LinkedListNode addListsReverse(LinkedListNode l1, LinkedListNode l2,
			int carry) {
		if (l1 == null && l2 == null && carry == 0) {
			return null;
		}

		// 新建当前结果节点
		LinkedListNode result = new LinkedListNode(carry, null, null);

		int value = carry;
		if (l1 != null) {
			value += l1.data;
		}
		if (l2 != null) {
			value += l2.data;
		}

		result.data = value % 10; // 设置当前结果节点值
		// 递归
		result.next = addListsReverse(l1 == null ? null : l1.next, l2 == null ? null
				: l2.next, value / 10);

		return result;
	}
	
	
	//===========================================
	// 当把值以顺序存放链表：
	// 如：         9->9->9
	// 		  	          + 1
	//     = 1->0->0->0
	public static LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2) {
		int len1 = length(l1);
		int len2 = length(l2);
		
		// 给较短的链表补零
		if(len1 < len2) {
			l1 = padList(l1, len2-len1);		// 9->9->9
		} else{
			l2 = padList(l2, len1-len2);		// 0->0->1
		}
		
//		System.out.println("pad1: " + l1.printForward());
//		System.out.println("pad2: " + l2.printForward());
		
		WrapperNode sum = addListsHelper(l1, l2);
		
		if(sum.carry == 0) {
			return sum.node;
		} else{		// 对于最后仍有进位的情况，如：999+1=1000
			LinkedListNode result = insertBefore(sum.node, sum.carry);
			return result;
		}
	}
	
	public static int length(LinkedListNode head) {
		if(head == null){
			return 0;
		} else{
			return 1 + length(head.next);
		}
	}
	
	// 递归，两个链表相加
	//     l1  l1.next
	// 9->9->9
	// 0->0->1
	//        ->0  head(carry:1)
	//      0->0 
	//    head(carry:1)
	public static WrapperNode addListsHelper(LinkedListNode l1, LinkedListNode l2) {
		if(l1 == null && l2 == null) {
			WrapperNode head = new WrapperNode();
			return head;
		}

		// 利用递归返回下一个节点之和以及carry，都封装在head里
		WrapperNode head = addListsHelper(l1.next, l2.next);
		int val = head.carry + l1.data + l2.data;		// 计算当前节点的和
		
		// 把当前节点插在旧的head之前，并保存新的carry值
		LinkedListNode newHead = insertBefore(head.node, val%10);
		return new WrapperNode(newHead, val/10);		// 返回新的wrapper，包含新头结点和carry
	}
	
	// 在head节点前面补上padding个零
	public static LinkedListNode padList(LinkedListNode head, int padding) {
		LinkedListNode cur = head;
		for(int i=0; i<padding; i++) {
			LinkedListNode newHead = new LinkedListNode(0, null, null);
			cur.prev = newHead;
			newHead.next = cur;
			cur = newHead;
		}
		return cur;
	}
	
	// 把新建的data节点添加到head之前，返回插入后的新建节点
	public static LinkedListNode insertBefore(LinkedListNode head, int data) {
		LinkedListNode node = new LinkedListNode(data, null, null);
		if(head != null) {
			head.prev = node;
			node.next = head;
		}
		return node;
	}
	
	// 把整数的链表形式转化为整数
	public static int linkedListToInt(LinkedListNode node) {
		int value = 0;
		while (node != null) {
			value = value * 10 + node.data;
			node = node.next;
		}
		return value;
	}
	
	public static class WrapperNode {
		public LinkedListNode node = null;
		public int carry = 0;
		public WrapperNode(){}
		public WrapperNode(LinkedListNode node, int carry){
			this.node = node;
			this.carry = carry;
		}
	}
	

	public static void main(String[] args) {
		LinkedListNode lA1 = new LinkedListNode(9, null, null);
		LinkedListNode lA2 = new LinkedListNode(9, null, lA1);
		LinkedListNode lA3 = new LinkedListNode(9, null, lA2);

		LinkedListNode lB1 = new LinkedListNode(1, null, null);
//		LinkedListNode lB2 = new LinkedListNode(0, null, lB1);
//		LinkedListNode lB3 = new LinkedListNode(0, null, lB2);

//		LinkedListNode list3 = addListsReverse(lA1, lB1, 0);
		LinkedListNode list3 = addLists(lA1, lB1);

		System.out.println("  " + lA1.printForward());
		System.out.println("+ " + lB1.printForward());
		System.out.println("= " + list3.printForward());

		 int l1 = linkedListToInt(lA1);
		 int l2 = linkedListToInt(lB1);
		 int l3 = linkedListToInt(list3);
		
		 System.out.print(l1 + " + " + l2 + " = " + l3 + "\n");
		 System.out.print(l1 + " + " + l2 + " = " + (l1 + l2));
	}

}