题目：
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode res = new ListNode(-1);
ListNode head = res;
while (l1 != null || l2 != null) {
int num = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val)
+ carry;
if(l1!=null){
l1 = l1.next;
}
if(l2!=null){
l2 = l2.next;
}
res.next = new ListNode(num % 10);
res = res.next;
carry = num / 10;
}
if(carry==1){
res.next = new ListNode(1);
}
return head.next;
}
}Input: (3->4->2)+(4->6->5)
Output: (8->0->7)
解析：拓展的这种解法看起来和原题差不多，实际上会更复杂更多，主要要注意两个问题。首先，因为两个链表的长度可能不一样，所以刚开始可以比较两个链表的长度，用0填充较短的链表；原题是求出新的节点后放在旧的节点后面，拓展题目需要添加节点到结果链表的头部，所以用递归调用解决。递归需要传递两个参数：结果链表节点和进位，可以创建内部类包含这两个参数，Java 实现代码如下所示：
/**
* Input: (3->4->2)+(4->6->5) Output: (8->0->7)
*/
public class AddTwoNumbersExp {
public static void main(String[] args) {
ListNode node11 = new ListNode(3);
ListNode node12 = new ListNode(4);
ListNode node13 = new ListNode(2);
ListNode node21 = new ListNode(4);
ListNode node22 = new ListNode(6);
ListNode node23 = new ListNode(5);
node11.next = node12;
node12.next = node13;
node21.next = node22;
node22.next = node23;
ListNode res = new AddTwoNumbersExp().addTwoNumbers(node11, node21);
while (res != null) {
System.out.print(res.val+" ");
res = res.next;
}
}
public class Node {
public ListNode sum = null;
int carry;
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 查询两个链表长度，将短的链表用0填充
int len1 = getLength(l1);
int len2 = getLength(l2);
l1 = len1 < len2 ? paddingZero(l1, len2 - len1) : l1;
l2 = len2 < len1 ? paddingZero(l2, len1 - len2) : l2;
// 对两个链表求和
Node sum = addTwoList(l1, l2);
// 判断是否有进位
if (sum.carry == 0) {
return sum.sum;
}
ListNode node = new ListNode(1);
node.next = sum.sum;
return node;
}
public int getLength(ListNode node) {
int length = 0;
while (node != null) {
length++;
node = node.next;
}
return length;
}
public ListNode paddingZero(ListNode l1, int zeroN) {
ListNode res = new ListNode(-1);
res.next = l1;
for (int i = 0; i < zeroN; i++) {
ListNode node = new ListNode(0);
node.next = res.next;
res.next = node;
}
return res.next;
}
public Node addTwoList(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) {
Node res = new Node();
return res;
}
Node after = addTwoList(l1.next, l2.next);
int val = after.carry + l1.val + l2.val;
ListNode cur = new ListNode(val % 10);
cur.next = after.sum;
Node res = new Node();
res.carry = val / 10;
res.sum = cur;
return res;
}
}
【leetcode】Add Two Numbers 解析以及拓展,布布扣,bubuko.com
【leetcode】Add Two Numbers 解析以及拓展
原文：http://blog.csdn.net/u013378502/article/details/38467895