当前位置 博文首页 > Add Two Numbers_让代码改变世界：LeetCode 2
这是LeetCode第二题，难度和第一题一样，也是Medium(中等)。
原题：
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
这其实是用链表“模拟”计算机中的整数相加的过程，理解上面并没有什么难度，实现上也比较容易。一般思路是取出各位依次相加，在这过程中要注意保留进位位。主要考察点应该在对链表的操作上面，我就是因为对链表操作不太熟悉，所以走了很多弯路，不过最终结果还是不错的，成绩为44ms，虽然在C++中属于中等偏下，但这毕竟只是开始，希望以后越做越好吧
本人的源代码：
<span style="font-size:14px;">class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* lhs=l1;//左操作数
ListNode* rhs=l2;//又操作数
ListNode* tempNode=new ListNode(0);
ListNode* sum=tempNode;//和
ListNode* pSum=sum;
int cf=0;//进位标识为
while(lhs!=NULL && rhs!=NULL){
int tempSum=lhs->val+rhs->val+cf;
ListNode* tempNode=new ListNode(tempSum%10);
pSum->next=tempNode;
if(tempSum-10>=0) {cf=1;}
else {cf=0;}
lhs=lhs->next;
rhs=rhs->next;
pSum=pSum->next;
}
while(lhs!=NULL){
int tempSum=lhs->val+cf;
ListNode* tempNode=new ListNode(tempSum%10);
pSum->next=tempNode;
if(tempSum-10>=0) cf=1;
else cf=0;
lhs=lhs->next;
pSum=pSum->next;
}
while(rhs!=NULL){
int tempSum=rhs->val+cf;
ListNode* tempNode=new ListNode(tempSum%10);
pSum->next=tempNode;
if(tempSum-10>=0) cf=1;
else cf=0;
rhs=rhs->next;
pSum=pSum->next;
}
if(cf==1){
ListNode* tempNode=new ListNode(1);
pSum->next=tempNode;
}
return sum->next;
}
};</span>代码虽然容易理解，但明显冗余度较大，所以又找了一个大神的精简代码，作为参考
大神代码：
<span style="font-size:14px;">class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode preheader(-1), *curr=&preheader;
int carry=0;
while(l1||l2||carry) {
curr->next = new ListNode(((l1?l1->val:0)+(l2?l2->val:0)+carry)%10);
curr = curr->next;
carry = ((l1?l1->val:0)+(l2?l2->val:0)+carry)/10;
l1?l1=l1->next:0;
l2?l2=l2->next:0;
}
return preheader.next;
}
};</span>总结：
这次并没有算法上的优劣比较，因为题目特性的原因，最简单直接的思路就是最有效的思路。而重点是对链表这种数据结构的操作熟练程度以及返回局部变量地址的方法的考察。
