题目：
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
思路：
从左到右相加，记录进位值。
注意：两个链表不同长度，及链表相加后也要检验进位是否为0。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
var carrybit=0,tempHead=new ListNode(0);
var p=tempHead; while(l1&&l2){
l1.val+=l2.val+carrybit;
carrybit=l1.val/10;
l1.val=l1.val%10;
p.next=l1;
p=p.next; l1=l1.next;
l2=l2.next; } var lp=(l1==null?l2:l1); while(lp){
if(carrybit==0){
p.next=lp;
break;
}else{
lp.val+=carrybit;
carrybit=lp.val/10;
lp.val=lp.val%10;
p.next=lp;
p=p.next;
}
lp=lp.next;
} if(carrybit!=0){
p.next=new ListNode(carrybit);
} return tempHead.next;
};
如果链表存储整数时，高位在前，该如何处理。
1、最简单的想法是，可以先把链表反转，然后调用上面的算法，最后把结果反转。
2、可不可以从高位向低位方向处理呢？我们知道进位是从低位传向高位的，如果从高位向低位方向计算，当计算到某一位需要进位时，有没有办法知道该进位传递到前面的哪一位呢？从以下几个例子来看：
从最高位到最低位我们依次记为第 1,2…,7位。图中红色标记的位置是：下一次需要进位时，进位的1放置的位子
第1位相加，结果为12，需要进位，这个进位放到第0位；同时标记第1位为下一次的进位标志
第2位相加，结果为3，不需要进位；标记第2位为下一次进位标志
第3位相加，结果为3，不需要进位；标记第3位为下一次进位标志
第4位相加，结果为9，不需要进位；此时进位标志不需要移动，因为9加上一个进位后还要继续向前进位
第5位相加，结果为9，不需要进位；此时进位标志不需要移动，因为9加上一个进位后还要继续向前进位
第6位相加，结果为14，需要进位，这个进位放到前面标记的第3位上，同时把第4位和第5位置0，标记第6位为下一次进位标志
第7位同上
所以综上所述，从高位往低位计算加法时，规则是：
一、如果当前位没有进位：（1）如果当前位的和小于9，则把改位设置成下一次进位标志（2）如果和等于9，进位标志不变
二、如果当前位有进位：把进位的1加到前面标志的位子上，同时把标志位和当前位之间的位全部置0（因为他们之间的位肯定全部都是9），把当前位设置成进位标志
上面我们举例的两个加数长度一致，如果长度不相同，则要先处理较长的整数的前面多出的部分。
我们把这一题leetcode的输入反转，测试代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
l1 = reverseList(l1);
l2 = reverseList(l2);
int n1 = lenList(l1), n2 = lenList(l2);
if(n1 < n2)//l1 指向较长的链表
{
swap(n1,n2);
swap(l1,l2);
}
//carryLoc是下一次出现进位时，进位的1将要放置的位子，pre指向当前结果链表的最后一个节点
//p1,p2分别是当前处理的l1,l2节点
//由于加数的最高位有可能进位，所以添加一个新的节点newHead
ListNode *newHead = new ListNode(), *carryLoc = newHead, *pre = newHead, *p1 = l1;
for(int i = ; i < n1-n2; i++)//处理l1高位长出的部分
{
if(p1->val < )carryLoc = p1;
pre->next = p1;
pre = p1;
p1 = p1->next;
}
ListNode* p2 = l2;
while(p1 != NULL)
{
pre->next = p1;
pre = p1; p1->val += p2->val;
if(p1->val > )
{
carryLoc->val += ;
for(carryLoc = carryLoc->next; carryLoc != p1; carryLoc = carryLoc->next)//carryLoc到p1之间的节点全部置0
carryLoc->val = ;
p1->val -= ;
}
if(p1->val < )
carryLoc = p1; p1 = p1->next;
p2 = p2->next;
}
if(newHead->val != )return reverseList(newHead);
else return reverseList(newHead->next);
}
//反转链表
ListNode *reverseList(ListNode *l1)
{
ListNode *p = l1->next, *pre = l1;
l1->next = NULL;
while(p)
{
ListNode *tmp = p->next;
p->next = pre;
pre = p;
p = tmp;
}
return pre;
}
//求链表长度
int lenList(ListNode *head)
{
int res = ;
while(head)
{
res++;
head = head->next;
}
return res;
}
};