每个链表表示一个数，从前向后，每个节点是该数的从低到高每一个十进制位的值，将两个链表相加，返回一个新链表。
【思路】
每次分别取两链的一个节点相加，有进位则累计到下一位。
思路简单，实现起来有很多细节要处理。
【my code】
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *p,*q,*r; ListNode *re=new ListNode(sizeof(ListNode)); p=l1; q=l2; r=re; int flag=0; while(p&&q){ r->val=p->val+q->val+flag; if(r->val>=10){ r->val%=10; flag=1; } else flag=0; p=p->next; q=q->next; if(p||q){ r->next=new ListNode(sizeof(ListNode)); r=r->next; } } while(p){ r->val=p->val+flag; if(r->val>=10){ r->val%=10; flag=1; } else flag=0; p=p->next; if(p){ r->next=new ListNode(sizeof(ListNode)); r=r->next; } } while(q){ r->val=q->val+flag; if(r->val>=10){ r->val%=10; flag=1; } else flag=0; q=q->next; if(q){ r->next=new ListNode(sizeof(ListNode)); r=r->next; } } if(flag==1){ r->next=new ListNode(sizeof(ListNode)); r=r->next; r->val=1; r->next=NULL; } else if(flag==0) r->next=NULL; return re; }
【评价】
超长无用代码的示范_(:зゝ∠)_ 耗时49ms，较为靠前。
有下面几点纠结了不少时间：
1.进位flag初始化0，每次计算要重新赋值，有进位赋值为1，无进位赋值为0，不要忽略无进位的情况，否则会每次都加1.——常见错误
2.re是否预留一个新节点，如果默认预留，最后又没有进位，则会多出一个节点，让该节点=NULL是不行的，在线运行会赋一个“随机”值，其实没有随机，但会告诉你多出一个节点。
所以只能每次判断是否需要预留节点。
3.分配新节点空间的代码太繁琐了，ListNode* tail = new ListNode(0); 这样就可以，因为struct中有默认构造函数。
来看看别人的解法吧。
【other code】
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) { int carry = 0; ListNode* tail = new ListNode(0); ListNode* ptr = tail; while(l1 != NULL || l2 != NULL){ int val1 = 0; if(l1 != NULL){ val1 = l1->val; l1 = l1->next; } int val2 = 0; if(l2 != NULL){ val2 = l2->val; l2 = l2->next; } int tmp = val1 + val2 + carry; ptr->next = new ListNode(tmp % 10); carry = tmp / 10; ptr = ptr->next; } if(carry == 1){ ptr->next = new ListNode(1); } return tail->next; }
【评价】
代码十分简洁，但耗时122ms！排名到了c#的范围！
可见有时候牺牲点代码长度还是值得的。
可以改进自己的代码：
flag=r->val/10;
r->val%=10;
省去了判断。
原文：http://www.cnblogs.com/ketchups-notes/p/4478501.html