日期：20180910
题目描述：
You are given two non-empty linked lists representing two non-negative integers. 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.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Examples：
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
详解：
这题难度为medium，难点有三：
这题的输出是一个链表，如果我们构建一个链表，最后一定得到的是链尾元素，但是函数返回的应该是链头元素，所以为了解决这个问题，将链头元素赋予一个额外的指针指向它。
另外，我们每次增添一个节点都要用到上一个节点的值，例如tmp->next = new ListNode(sum%10)，tmp就是上一个节点。但是第一个节点怎么办，第一个节点没有上一个节点。解决办法就是牺牲头节点，第一个节点随便赋一个值，从然后让tmp和result都指向它，之后开始循环。最后返回result->next。
-
如果声明一个指向链表节点的指针，之后直接用的话会报错。
ListNode* result； result->val = 0；//会报错member access within null pointer of type ‘struct ListNode’因为这么做相当于声明了一个指针，却没有赋初值，编译器并不知道result指向哪里。这里如果想解决这个问题就要用到动态内存了。
ListNode* result = new ListNode(0); cout<<result->val; //会正确的输出0。用动态内存new运算符，自动为新的节点分配一块内存，内存地址也会返回到result，result也就成为了指向该地址的指针。
知道了这三个难点，程序设计起来便不会太费劲。
/**
* 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) {
ListNode *result = new ListNode(0);
ListNode *tmp = result;
int sum = 0;
while(l1 || l2){
if(l1){
sum += l1->val;
l1 = l1->next;
}
if(l2){
sum += l2->val;
l2 = l2->next;
}
tmp->next = new ListNode(sum%10);
sum /= 10;
tmp = tmp->next;
}
if(sum)
tmp->next = new ListNode(1);
return result->next;
}
};
提交答案之后用时是50ms，看了一下28ms的答案，如下所示：
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *tail = new ListNode(0);
ListNode *result = tail;
bool carry = false;
while(l1 != NULL || l2 != NULL) {
int x = 0;
int y = 0;
if (l1 != NULL) {
x = l1->val;
l1 = l1->next;
}
if (l2 != NULL) {
y = l2->val;
l2 = l2->next;
}
int sum = x + y;
if (carry) {
sum += 1;
carry = false;
}
if (sum >= 10) {
carry = true;
sum -= 10;
}
tail->val = sum;
if (l1 != NULL || l2 != NULL) {
tail->next = new ListNode(0);
tail = tail->next;
}
}
// Add the last carried digit, if there is one.
if (carry) {
tail->next = new ListNode(1);
tail = tail->next;
}
return result;
}
};
其实和我的基本是一样的，只不过针对刚才说的难点2，他的解决方法不一样。我是先判断好这次能不能在之前的节点后新加节点，如果能就新加一个。而他的思路是，把当前节点的val改成sum值，然后如果接下来还有就新增加一个节点留着下次用，如果算完了就不加了，最后还是指向NULL。然后全部结束后还得判断一下有没有进位，如果有还得再添一个1。
我的办法代码简洁，但是想的时候我头很大，他的办法容易想，不过判断各种条件比较麻烦。在我的印象中老外写代码总是很简单粗暴。不过他的代码和我的计算速度还是在一个数量级，毕竟方法基本一样的，他的快一点可能以为一些其他玄学因素吧。
