前言：这是一道很有意思的题目，原题如下：
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 to say you have to calculate 617+295 and return output:
Output: 2 -> 1 -> 9
Follow UP:
Suppose the digits are store in forward order, repeat the above problems
Input: (6 -> 1 -> 7), (2 -> 9 -> 5). That is to say you have to calculate 617+295 and return output:
Output: 9 -> 1 -> 2
译文：
你有两个由单链表表示的数。每个结点代表其中的一位数字。数字的存储是逆序的， 也就是说个位位于链表的表头。写一函数使这两个数相加并返回结果，结果也由链表表示。
例子：(7-> 1 -> 6), (5 -> 9 -> 2)
输入：2 -> 1 -> 9
进阶：
考虑链表是反向的，比如：
例子：(6-> 1 -> 7), (2 -> 9 -> 5)
输入：9 -> 1 -> 2
考虑递归法与非递归法实现原题和进阶问题（Follow Up）。
非递归方法：
我们必须保存每次结果的carryOn即进位值，在第一种情况下，我们需要知道，表头的数据是最低位，这意味着从表头即可开始加两个数，并且把carryOn （1，或0）合理的传递给下一次运算。
首先建立链表类如下：
private static class LinkedList{
private Node head;
public LinkedList (){
this.head = null;
}
public void insertNode (int value){
Node newNode = new Node(value);
newNode.prev = null;
newNode.next = this.head;
if (this.head!=null) this.head.prev = newNode;
this.head = newNode;
}
public void deleteNode(Node tobeDel){
//System.out.println("deleting:value["+tobeDel.value+"]"+tobeDel.next);
if (tobeDel == this.head) {
head = tobeDel.next;
head.prev = null;
}
if (tobeDel.prev!=null) tobeDel.prev.next = tobeDel.next;
if (tobeDel.next!=null) tobeDel.next.prev = tobeDel.prev;
}
public void printAllNodes(){
Node newNode = this.head;
while (newNode!=null){
if (newNode == head)
System.out.print("[Head]"+newNode.value);
else
System.out.print("->"+newNode.value);
newNode = newNode.next;
}
System.out.println("[End]");
}
}
注意我同时建立了函数printAllNodes为了方便的打印所有链表。
下面是Node的类：
private static class Node{
private int value;
private Node next;
private Node prev;
public Node (int value){
this.value = value;
this.prev = null;
this.next = null;
}
}
核心代码：
private static void CC2_5_1() {
// TODO Auto-generated method stub
LinkedList list1 = new LinkedList();
LinkedList list2 = new LinkedList();
LinkedList newList = new LinkedList();
list1.insertNode(6);
list1.insertNode(1);
list1.insertNode(7);
list2.insertNode(2);
list2.insertNode(9);
list2.insertNode(5);
list1.printAllNodes();
list2.printAllNodes();
Node point1 = list1.head;
Node point2 = list2.head;
int value=0,carryOn=0;
while (point1 !=null && point2 !=null){
value = point1.value + point2.value + carryOn;
carryOn = 0;
if (value >= 10){
value = value%10;
carryOn = 1;
}
newList.insertNode(value);
point1 = point1.next;
point2 = point2.next;
}
point1 = newList.head;
while (point1!=null){
newList.insertNode(point1.value);
newList.deleteNode(point1);
point1 = point1.next;
}
newList.printAllNodes();
}
递归方法实现FollowUp问题
当链表反转，即表尾变成了加运算的最低位时，上述方法变的相对麻烦很多，这时递归方法显得更加方便。
核心代码：
private static int addingTwoLinkedList(LinkedList newList,Node n1, Node n2){
int value = n1.value + n2.value;
if (n1.next ==null && n2.next == null){
newList.insertNode(value%10);
return value/10;
}
else{
value = value + addingTwoLinkedList(newList,n1.next,n2.next);
newList.insertNode(value%10);
return value/10;
}
}
函数addingTwoLinkedList的返回值是向其上层（previous Node）进位的数值，非0即1. 函数的参数需要输入两个被加数的表头即可。
递