等长链表单扫描求和
两个单链表（singly linked list），每一个节点里面一个0-9的数字， 输入就相当于两个大数了。然后返回这两个数的和（一个新list）。这两个输入的list 长度相等。 要求是：
- 不用递归。
- 要求算法在最好的情况下，只遍历两个list一次， 最差的情况下两遍。
下面这个方法也只是看上去很美，其实也不是遍历了一遍，一前一后两个指针不也遍历了两遍吗。所以我还是倾向于生成结果链表，再逆置然后处理进位再逆置。
既然只能遍历两个输入链表一次，那我们就从高位加起呗。在这种限制条件下， 这是唯一的出路。然后呢？进位咋整？先加高位，再加低位， 低位产生的进位怎么加到高位去？我们可没有前向指针哦亲。既然没有前向指针， 我们就让一个临时指针指向高位，当低位相加产生进位时，我们就可以操作高位了。 让我们看看图示：
输入链表1： 1 2 3
输入链表2： 1 2 8
输出链表： 2 4
两个指针： p q 当指向输出链表当前结点的指针q发现3+8=11，产生进位，指向高位的p就将结点值加1。 注意，两个0-9的数相加，要么不进位，要么进位为1，只有两种情况。因此， 我们不用考虑进位是其它数，这一点很重要，后面会看到的。
这样就OK了吗？当然不是，如果你遇上连续进位，怎么破？请看下面的情况：
输入链表1： 1 2 3 4 5
输入链表2： 1 7 6 5 9显然，指向高位的指针p总是紧跟着指向当前结点的指针q是不行的， 这样当遇上连续进位时，比p更高位的位也需要改变。既然p不能紧跟着q， 我们就不让它们紧挨着，给它们产生点距离。考虑一下，什么情况下会产生连续进位？ 9! 嗯，遇上9的时候。它要连续进位到哪一位？不为9的那一位。因此，指针p 要停留在和不为9的那一位上，看图示：
输入链表1： 1 2 3 4 5
输入链表2： 1 7 6 5 9
输出链表： 2 9 9 9
两个指针： p q 这回当q发现，需要进位了，只需要把p所指结点加1，然后把p，q间的结点都置0即可。 为什么都置0了呢，因为进位只可能是1，9+1=10，留在该位的自然是0了。
分析完毕，这种方法在任何时候都只需要遍历输入链表一次，空间复杂度O(1)。
#include<iostream>
#include<vector>
#include<string>
using namespace std;
struct ListNode
{
int val;
ListNode* next;
ListNode(int v):val(v),next(NULL){}
};
ListNode* addTwo(ListNode* l1,ListNode* l2)
{
ListNode guard(-1);
ListNode* pNine=NULL,*tail=&guard;
while(l1&&l2)
{
ListNode* tmp=new ListNode(l1->val+l2->val);
tail->next=tmp;
tail=tail->next;
if(tmp->val>=10)
{
if(pNine==NULL)
{
ListNode* head=new ListNode(0);
head->next=guard.next;
guard.next=head;
pNine=head;
}
pNine->val++;
pNine=pNine->next;
while(pNine!=tmp)
{
pNine->val=0;
pNine=pNine->next;
}
tmp->val=0;
pNine=tmp;
}
else if(tmp->val<9)
{
pNine=tmp;
}
l1=l1->next,l2=l2->next;
}
return guard.next;
}
ListNode* create(int n)
{
ListNode head(-1);
ListNode* tail=&head;
while(n--)
{
tail->next=new ListNode(0);
cin>>tail->next->val;
tail=tail->next;
}
return head.next;
}
int main()
{
while(1)
{
int n;
cin>>n;
ListNode* l1=create(n);
ListNode* l2=create(n);
ListNode* res=addTwo(l1,l2);
cout<<endl;
}
}