2. Add Two Numbers

题目描述：给两个用非空链表表示的非负整数，数字从低位到高位是从左到右排列的，每个节点只包含数的一位。将这两个数的链表加为一个返回。如：

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

分析：模拟遍历两链表，时间复杂度O(n + m)，空间O(n)。

代码：

/**
 * 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 l(-1);
        int c = 0;
        ListNode *pre = &l;
        for (ListNode *pa = l1, *pb = l2; pa != nullptr || pb != nullptr; pa = pa == nullptr? nullptr : pa -> next, pb = pb == nullptr? nullptr : pb -> next, pre = pre -> next)
        {
            int ai = pa == nullptr? 0 : pa -> val;
            int bi = pb == nullptr? 0 : pb -> val;
            int v = (ai + bi + c) % 10;
            c = (ai + bi + c) / 10;
            pre -> next = new ListNode(v);
        }
        if (c > 0)
            pre -> next = new ListNode(c);
        
        return l.next;
    }
};