Leetcode-2.两数相加

（隐含大数相加）

1.错误解法

idea: 先遍历两个链表，计算出两个数的数值（十进制），后将两数相加，再将和的各位转换为链表的各个节点值。

个人觉得想法是完全没错的，但是要知道计算机一次所能存储的数字位数有限，有的样例就过不去（尽管我使用了long long类型）。比如：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
12         long long value1 = 0, value2 = 0;
13         long long count1 = 0, count2 = 0;
14         //计算两个数
15         while(l1)
16         {
17             value1 += l1->val*pow(10, count1);
18             l1 = l1->next;
19             count1++;
20         }
21         while(l2)
22         {
23             value2 += l2->val*pow(10, count2);
24             l2 = l2->next;
25             count2++;
26         }
27         //求和->转换->加入单链表
28         long sum = value1+value2;
29         ListNode* ans, *p, *temp;
30         ans = new ListNode(sum%10);
31         p = ans;
32         sum /= 10;
33         while(sum)
34         {
35             //尾插法
36             temp = new ListNode(sum%10);
37             p->next = temp;
38             p = temp;
39             sum /= 10;
40         }
41         return ans;
42     }
43 };

错误解法（先遍历求和再转换）

2.正解

idea：（参考了官方题解）遍历两个链表（p， q），节点不为空取值，为空则取0，需要另外加入一个进位量（carry）来表示进位，将两个链表值与进位值相加，和取余建立新节点（更新carry=sum/10），最后处理一下最后可能的进位（再新建一个节点）。

 1 class Solution {
 2 public:
 3     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
 4         ListNode *Head, *p, *q, *current;//待返回链表头节点
 5         Head = new ListNode(0);
 6         p = l1; q = l2; current = Head;
 7         int carry = 0;//进位
 8         while(p != NULL || q != NULL)
 9         {
10             int x = (p != NULL)?p->val:0;
11             int y = (q != NULL)?q->val:0;//不为空则取值，为空取0
12             int sum = carry + x + y;
13             carry = sum/10;
14             current->next = new ListNode(sum%10);//余数即为节点值
15             current = current->next;
16             if(p != NULL)
17             {
18                 p = p->next;
19             }
20             if(q != NULL)
21             {
22                 q = q->next;
23             }
24         }
25         if(carry > 0)//处理最后的进位
26         {
27             current->next = new ListNode(carry);
28         }
29         return Head->next;
30     }
31 };

正解C++