1. 题目描述

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.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

2. 初解

在刚上手这道题的时候，受到了题目的误导。Input链表中的数字是逆序的，最终要求输出的链表也要逆序，我的思路太僵了，就想着先把输入转换为可以直接处理的数字(int)，再相加后逆序输入Output链表。结果这种方法受到了测试用例的降维打击，题目里的样例出现了1000000000000000000000000001这种无法用任何一种c语言原生类型直接存储的数，结果毫无疑问Wrong Answer了。

此路不通就是在提醒做题的人换一种思路，无奈我的思路太少，没想到替代方法。只能看LeetCode给的官方solution借鉴思路。

官方solution的思路是，刚好两个input链表也是逆序的，那就说明head node存储的是最低位，而整数相加恰好就是从最低位依次往上加，所以直接同时遍历两个input链表的每一位再同时把每一位的和输入给output链表就行了，代码如下：

#include <stdlib.h>
#include <stdio.h>

struct ListNode    {
    int val;
    struct ListNode* next;
};

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    int carry = 0, sum = 0;
    int val1 = 0, val2 = 0;
    struct ListNode* ptr1 = l1;
    struct ListNode* ptr2 = l2;
    struct ListNode* dummyRes = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* curr = dummyRes;
    dummyRes->val = 0;

    while(ptr1 || ptr2) {
        val1 = (ptr1) ? (ptr1->val) : (0);
        val2 = (ptr2) ? (ptr2->val) : (0);
        sum = val1 + val2 + carry;
        carry = sum / 10;
        curr->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        curr->next->val = sum % 10;
        curr = curr->next;
        if(ptr1) ptr1 = ptr1->next;
        if(ptr2) ptr2 = ptr2->next;
    }
    if(carry) {
        curr->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        curr->next->val = carry;
        curr->next->next = NULL;
    } else {
        curr->next = NULL;
    }
    return dummyRes->next;
}

官方solution中同时用到了很多tricks，用上这些技巧会使你的代码的逻辑大大简化，像我初步了解了这种方法的原理后尝试自己把解法编写出来，结果因为一些地方的判断逻辑太复杂，结果最后还是没写出来，可以说是十分的挫败了。

第一个trick是关于何时需要malloc下一个节点的空间，因为得判断出下一个节点一定有数字才需要malloc。solution中建立了头节点dummyRes，而顾名思义，这个是假的头节点，这个节点的next才是最终要返回的头节点。这种做法使得判断是否需要malloc的逻辑变得简单了。如果 直接建立res当作头结点的话，需要在循环里用多余的判断逻辑来判断是否malloc。

第二个trick是当要相加的两个input的位数不一样时，必定有一个input会先计算到链表的末尾，而这个input对应的ptr这时就不应该继续往后走了，solution用了一个简单的判断就解决了这个问题：

if(ptr1) ptr1 = ptr1->next;
if(ptr2) ptr2 = ptr2->next;

只有当ptr不为NULL时才让ptr向后走，否则就让ptr一直停留在NULL上。
我编写的时候就没想到这样做，而是想当一个链表遍历完后直接退出循环，再把另一个没遍历完的链表接在res后面，而这种方法要加上许多判断逻辑，远不如另一种方法简单。