[数据结构与算法]2. 两数相加（大数加法）

解法：大数加法模拟

技巧：对于链表，可申请哑节点（dummy），便于管理头节点。
加法过程：相应位的和用一个数$temp$临时保存。在这过程中会用到两个值，一个是当前位的非进位和，可以用$temp\%10$；另一个是进位，可以用$temp/10$得到。
最后，加法做完后，如果进位不为0，直接赋给最高位（当前最高位的下一位）。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    // dummy节点方便使用链表，可将头节点当作普通节点处理
    struct ListNode *dummy = malloc(sizeof(struct ListNode));
    dummy->next = NULL;
    struct ListNode *tempNode = dummy;

    // carry保存进位值
    int carry = 0;

    while(l1 || l2)
    {
        // l1或者l2当前位有值,申请一个节点用来保存当前位的非进位和
        tempNode->next = malloc(sizeof(struct ListNode));
        tempNode = tempNode->next;
        tempNode->next = NULL;
        // temp临时保存相应位的和
        int temp = carry;

        if(l1)
        {
            temp += l1->val;
            l1 = l1->next;
        } 
        if(l2)
        {
            temp += l2->val;
            l2 = l2->next;
        } 
        // 取个位作为当前位的值
        tempNode->val = temp % 10;
        // 取十位作进位值
        carry = temp / 10;
    }

    // 如果进位不为0，需要申请一个节点作为最高位，直接赋值给最高位
    if(carry)
    {
        tempNode->next = malloc(sizeof(struct ListNode));
        tempNode = tempNode->next;
        tempNode->next = NULL;
        tempNode->val = carry;
    }
    // dummy节点没用了，应该释放，避免内存泄漏
    tempNode = dummy->next;
    free(dummy);
    return tempNode;
}

时间复杂度$O(n)$：需要遍历$l1$和$l2$。
空间复杂度$O(1)$：返回的链表不计入其中。